Binary search, grown into a tree
Lesson 1-3's binary search was brilliant but brittle. It needs a sorted array, and lesson 2-3 showed that inserting into an array is O(n), so keeping the array sorted costs more than the search saves. The question this lesson answers is what happens when the halving lives in the structure itself.
A binary search tree, or BST, is a binary tree with one rule holding at every node.
Everything in the left subtree is smaller than the node, and everything in the right subtree is bigger.
Searching then becomes the guessing game walked downward. At each node, compare and go left or right, and each step discards an entire subtree in the same way each binary-search check discarded half the array.
That gives three operations worth stating together.
- search costs O(height).
- insert walks the same path and attaches a new leaf wherever it falls off the tree, also O(height), with no shifting at all.
- inorder traversal visits left, node, right, which by the BST rule is ascending order, so a sorted listing is available at any moment for free.
Note that the costs are stated in height rather than in n. That distinction looks pedantic until the second half of this lesson, where it turns out to be the whole story.
Insert, search, and a free sorted listing
Seven numbers inserted, then an inorder traversal and two searches with a check counter.
class Node: def __init__(self, value): self.value = value self.left = None self.right = None def insert(root, value): if root is None: return Node(value) if value < root.value: root.left = insert(root.left, value) elif value > root.value: root.right = insert(root.right, value) return root def search(root, value): checks = 0 node = root while node is not None: checks += 1 if value == node.value: return True, checks node = node.left if value < node.value else node.right return False, checks def inorder(node, out): if node is None: return inorder(node.left, out) out.append(node.value) inorder(node.right, out) root = None for v in [50, 30, 70, 20, 40, 60, 80]: root = insert(root, v) out = [] inorder(root, out) print("inorder:", out) print("search 60:", search(root, 60)) print("search 65:", search(root, 65))
Output
inorder: [20, 30, 40, 50, 60, 70, 80] search 60: (True, 3) search 65: (False, 3)
insert returns the subtree root, which is why the caller writes root = insert(root, v). The if root is None: return Node(value) line is where the new leaf appears, at the exact spot the walk fell off the tree.
The elif value > root.value is deliberate. An equal value matches neither branch, so duplicates are ignored rather than stored twice.
search is iterative, and the ternary line does the halving: smaller goes left, otherwise right, with no need to remember anything.
The numbers went in unsorted and came out sorted, with no sorting step anywhere. That is the BST rule doing the work, since inorder is defined to take the smaller side first.
Both searches used 3 checks in a tree of 7 values, and the miss cost the same as the hit. That is O(height), and the height here is 2, so the walk from root to leaf is 3 nodes.
The walk for 65 goes 50, then 70, then 60, and then falls off 60's right side without finding it.
Each step is one comparison. 65 > 50 sends it right to 70, 65 < 70 sends it left to 60, and 65 > 60 sends it right again, where 60 has no right child, so the search ends after 3 checks with a miss.
The efficiency is in what never got looked at. Four of the seven nodes, the whole left subtree under 30, were discarded by the very first comparison and never visited.
The falling-off is also exactly where an insert would act. Calling insert(root, 65) would follow this identical path and attach 65 as 60's right child, which is why search and insert share a cost.
The balance catch
O(height) is only as good as the height. Inserting [50, 30, 70, 20, 40, 60, 80] produced a balanced tree of height 2, where searches took at most 3 checks.
Now insert [10, 20, 30, 40, 50, 60, 70], already sorted. Every value is larger than the one before it, so every insert goes right, and the tree degenerates into a chain of right children.
At that point every node has exactly one child, which means the structure is a linked list wearing a tree's class definition. Each comparison discards a single node rather than a subtree, and search is back to O(n).
The two extremes are worth stating plainly.
- A balanced BST has height ≈ log₂ n, giving O(log n) search, insert, and delete.
- A degenerate BST has height ≈ n, giving O(n) for everything.
The uncomfortable part is that sorted input is not a rare adversarial case, it is one of the most common ways real data arrives.
Production systems solve this with self-balancing BSTs, the AVL and red-black trees, which perform small local rotations on insert to keep the height O(log n) no matter what order the data comes in. Their mechanics belong to the Algorithms course, and what matters here is knowing why balance is the whole ballgame.
Measuring the balance catch
The same 15 values inserted in two different orders, with the height reported for each.
class Node: def __init__(self, value): self.value = value self.left = None self.right = None def insert(root, value): if root is None: return Node(value) if value < root.value: root.left = insert(root.left, value) elif value > root.value: root.right = insert(root.right, value) return root def tree_height(root): if root is None: return -1 return 1 + max(tree_height(root.left), tree_height(root.right)) good_order = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15] sorted_vals = sorted(good_order) for name, values in [("good order", good_order), ("sorted", sorted_vals)]: root = None for v in values: root = insert(root, v) print(name, "n =", len(values), "height =", tree_height(root))
Output
good order n = 15 height = 3 sorted n = 15 height = 14
tree_height returns −1 for an empty tree, which is the convention that makes a single leaf come out as 1 + max(−1, −1) = 0. Beyond that base case it mirrors lesson 7-1's height function exactly.
The two results come from identical data. The good order inserts each level's values before the next, filling the tree evenly for the ideal height of 3, since a perfect tree of 15 nodes has levels 0 through 3.
Sorted order builds a 14-deep chain instead, which is the worst possible shape. A search in that tree costs up to 15 comparisons against 4 in the balanced one, and the gap widens with n: at a million values it is roughly a million against twenty.
The lesson for anyone writing a plain BST is direct. If the insertion order is or might be sorted, the structure silently stops being a search tree, and either shuffling the input or using a self-balancing variant is required.
About 20 comparisons.
A balanced BST has height ≈ log₂(1,000,000) ≈ 20, and a search does one comparison per level while discarding a subtree at each step.
That is binary search's arithmetic exactly, and lesson 1-3 already computed it: the halvings program printed 19 for a million. The BST just relocates the same halving from an array's index math into the shape of the structure.
What the tree buys with that relocation is insertion. A sorted array also searches in about 20 steps, but adding a value costs O(n) shifting, while the BST attaches a leaf in O(log n).
The other two answers name the failure modes rather than the structure. 500,000 is roughly the average cost of scanning an unsorted list, and 1,000 is nothing this structure does at all.