Binary Search Tree

A plain binary tree has no rule about where values go. Values are placed wherever there was room, with no order to guide a search.

Say we're searching for 65 in this tree. With no ordering rule, there's no way to know whether to go left or right at any node, 65 could be anywhere. The only option is to check nodes one by one until it turns up:

Output:????

Four nodes checked just to find one value, in a tree of only six nodes. In the worst case, a search like this has to visit every node.

Key Idea

Adding one ordering rule turns this same shape into a structure that supports much faster search, without checking every node.

Definition

A Binary Search Tree (BST) is a binary tree where, for every node, all values in its left subtree are smaller than the node's value, and all values in its right subtree are larger than the node's value. This rule applies recursively: it holds at the root, and again at every node inside each subtree.

Even in this small tree, the rule holds: 30 < 50 < 70. The rest of this page builds a larger tree from empty, using the insertion algorithm below, and reuses it for searching.

Insertion

Key Idea

Inserting a value means walking down the tree comparing the new value against each node, going left if smaller and right if larger, until an empty spot is found. The new value is placed there.

INSERT(ROOT, KEY)
 
1. If ROOT == NULL:
       Create and return new node with KEY.
2. If KEY < ROOT->data:
       ROOT->left = INSERT(ROOT->left, KEY)
3. Else if KEY > ROOT->data:
       ROOT->right = INSERT(ROOT->right, KEY)
4. Return ROOT.

Every newly inserted node becomes a leaf, since insertion always walks until it finds an empty position, never replacing an existing node.

Building a BST from empty

Inserting 50, 30, 70, 20, 40, 60, 80 in that order, an empty tree to begin with:

Insert 50. The tree is empty, so 50 becomes the root:

Insert 30. Since 30 < 50, it goes to the left of 50:

Insert 70. Since 70 > 50, it goes to the right of 50:

Insert 20. Since 20 < 50, go left. Since 20 < 30, it goes to the left of 30:

Insert 40. Since 40 < 50, go left. Since 40 > 30, it goes to the right of 30:

Insert 60. Since 60 > 50, go right. Since 60 < 70, it goes to the left of 70:

Insert 80. Since 80 > 50, go right. Since 80 > 70, it goes to the right of 70:

Final tree. Every node obeys the rule: at 50, everything on the left (20, 30, 40) is smaller, everything on the right (60, 70, 80) is larger. The same rule holds recursively at every subtree, e.g. at 30, 20 < 30 < 40.

Insertion time complexity

Balanced / average case: O(log n)

Worst case: O(n)

Why BST search is fast

Key Idea

The ordering rule means that at every node, a single comparison eliminates an entire subtree from consideration, not just one value.

Searching for 60 in the tree built above:

At 50: 60 > 50, so the entire left subtree (20, 30, 40) is discarded, go right.

At 70: 60 < 70, so the entire right subtree (80) is discarded, go left.

At 60: match, found.

Three comparisons eliminated six other values without visiting them individually, that's what makes BST search fast on a well-shaped tree.

SEARCH(ROOT, KEY)
 
1. If ROOT == NULL:
       Return NOT FOUND
2. If KEY == ROOT->data:
       Return FOUND
3. If KEY < ROOT->data:
       Return SEARCH(ROOT->left, KEY)
4. Else:
       Return SEARCH(ROOT->right, KEY)

Search time complexity

Balanced / average case: O(log n)

Worst case: O(n)

The worst case happens when the tree is skewed, each comparison then eliminates nothing, since there's no branching left to discard.

A BST degrades into exactly this skewed shape when values are inserted in already-sorted order. Each new value is larger than every node so far, so it always goes right, and never left.

Inserting 10, 20, 30, 40 in that order into an empty tree:

Every node has only a right child, a right-skewed tree. Searching for 40 now takes 4 comparisons instead of the 2 a balanced 4-node tree would need, since there's no branch to skip.

Finding the minimum and maximum value in a BST

Because smaller values always go left and larger values always go right, the minimum and maximum values in the tree sit at predictable positions, found with no comparisons beyond following one direction:

Minimum = leftmost node   (keep following ->left until NULL)
Maximum = rightmost node  (keep following ->right until NULL)

MINIMUM(ROOT)
while ROOT->left != NULL:
    ROOT = ROOT->left
return ROOT

MAXIMUM(ROOT)
while ROOT->right != NULL:
    ROOT = ROOT->right
return ROOT

BST and inorder traversal

Key Idea

Inorder traversal of a BST always produces values in sorted order. This follows directly from the ordering rule: inorder visits left subtree (smaller values), then root, then right subtree (larger values), at every level.

For the tree built above, inorder gives: 20 30 40 50 60 70 80, already sorted.

Quick recall

BST rule: for every node, left subtree < node < right subtree, applied recursively at every level.
Search and insertion both follow the same downward comparison path: O(log n) balanced, O(n) worst case (skewed tree).
Every inserted value becomes a new leaf.
Minimum is the leftmost node, maximum is the rightmost node, found by following one direction to the end.
Inorder traversal of a BST always yields sorted order.