Special Properties of a Binary Search Tree

Special Properties of a Binary Search Tree

A binary search tree is just a binary tree that follows one simple rule. We call this rule the binary search property. It says that for every node in the tree:

• All values in the left subtree are *smaller* than the node.
• All values in the right subtree are *larger* than the node.

A "subtree" is just the smaller tree that hangs below a node. The left subtree is everything on its left side, and the right subtree is everything on its right side.

Because every node follows this one rule, the whole tree becomes very organized. And that organization gives us some neat properties that we can use again and again. Let's look at them using this example tree:

        50
       /  \
      20    64
     / \   /  \
    12 35 63   80

Finding the Minimum Value

Think about the rule: the left side of any node is always smaller. So if you keep moving left, you keep moving toward smaller and smaller values.

To find the smallest value in the tree, just start at the top (the root, which is 50) and keep going left until you cannot go left anymore:

• Start at 50, go left to 20.
• From 20, go left to 12.
• 12 has no left child, so stop.

The last node you reach is 12, the minimum value. The smallest value always lives at the leftmost node of the tree.

Finding the Maximum Value

This is the mirror image of finding the minimum. The right side of any node is always larger. So to find the biggest value, start at the root and keep going right until you cannot go right anymore:

• Start at 50, go right to 64.
• From 64, go right to 80.
• 80 has no right child, so stop.

The last node you reach is 80, the maximum value. The largest value always lives at the rightmost node of the tree.

Inorder Traversal Gives a Sorted List

A traversal simply means visiting every node in the tree in some order. The inorder traversal follows this pattern for each node:

1. Visit the left subtree first.
2. Then visit the node itself (the center).
3. Then visit the right subtree.

We call this left, center, right.

Here is the magic: because the left side is always smaller and the right side is always larger, inorder traversal visits the values from smallest to largest. You always get a sorted list in ascending order.

For our example tree, the inorder traversal gives:

12  20  35  50  63  64  80

This is a very useful fact. If you ever need the values of a binary search tree in sorted order, you do not have to sort them — the tree already holds them in a way that produces sorted output for free.

Reverse Inorder Traversal Gives a Reverse-Sorted List

If you flip the inorder pattern around, you get the reverse inorder traversal. Here the pattern is right, center, left (sometimes written as RNL):

1. Visit the right subtree first.
2. Then visit the node itself.
3. Then visit the left subtree.

Since you now visit the larger side first, the values come out from largest to smallest. You get a descending (reverse sorted) list.

For our example tree, the reverse inorder traversal gives:

80  64  63  50  35  20  12

Quick Recap

• The minimum value is the leftmost node — keep going left.
• The maximum value is the rightmost node — keep going right.
• Inorder traversal (left, center, right) gives values in ascending sorted order.
• Reverse inorder traversal (right, center, left) gives values in descending sorted order.

All of these come from one single rule: left is smaller, right is larger.