Binary Search Trees

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 inserting into an array is O(n). What if the halving lived in the structure itself?

A binary search tree (BST) is a binary tree with one rule at every node:

everything in the left subtree is smaller than the node, everything in the right subtree is bigger.

Then searching is the guessing game walked downward: at each node, compare and go left or right. Each step discards an entire subtree, just like each binary-search check discarded half the array.

• search: O(height)
• insert: walk the same path, attach a new leaf where you fall off. O(height), no shifting!
• inorder traversal: visits left-node-right, which by the BST rule is ascending order. A free sorted listing at any moment.

The balance catch

O(height) is only as good as the height. Insert [50, 30, 70, 20, 40, 60, 80] and the tree comes out balanced: height 2, searches ≤ 3 checks.

Now insert [10, 20, 30, 40, 50, 60, 70], already sorted. Every value is bigger than the last, so every insert goes right: the "tree" degenerates into a chain of right children. Every node now has exactly one child, so the "tree" is structurally a linked list — each comparison discards a single node instead of a whole subtree, and search is back to O(n).

So:

• balanced BST: height ≈ log₂ n → O(log n) search, insert, delete
• degenerate BST: height ≈ n → O(n) everything

Production systems use self-balancing BSTs (AVL and red-black trees) that do small local rotations on insert to keep height O(log n) guaranteed. Their mechanics belong to the Algorithms course. Your job now: know why balance is the whole ballgame.