The binary search tree (BST)

The key property of the BST

A binary search tree (BST) is a binary tree that follows a strict rule at every node: all the values in its left subtree are smaller than it, and all the values in its right subtree are greater than it. This rule applies to every node in the tree, not just the root.

A big complete example

                    8
                  /   \
                 3     10
                / \       \
               1   6        14
                  / \      /
                 4   7    13

Let's check the rule on a few nodes:

• root 8: left subtree (3, 1, 6, 4, 7) all < 8; right subtree (10, 14, 13) all > 8. (correct)
• node 6: left subtree (4) < 6; right subtree (7) > 6. (correct)
• node 14: left subtree (13) < 14; no right subtree. (correct)

Why this structure is useful

Thanks to this rule, searching for a value comes down to choosing at each node "do I go left or right?", exactly like a binary search. In a well-balanced tree of n values, a search costs only on the order of log2(n) comparisons, instead of n comparisons in an unsorted list.

In-order traversal recovers the sorted order

A remarkable property: if you read a BST with an in-order traversal (left, root, right), you always get the values sorted in ascending order. On the tree above: 1, 3, 4, 6, 7, 8, 10, 13, 14.

Common pitfall

A frequent mistake is to check the "left < node < right" rule only at the root. The rule must hold at every node, over all of its subtree, not just with its direct child: a node far to the right within the root's left subtree must still remain smaller than the root.