BST · Stage 1 of 3
BST Search & Pruning
Use the left < node < right invariant to discard half the tree at each step
Foundations
A binary search tree, or BST, is a binary tree of TreeNodes with one ordering rule at every node: every value in its left subtree is smaller, and every value in its right subtree is larger, left < node < right. The rule freezes binary search into the tree: one comparison at a node rules out a whole subtree. A search from the root follows one path, so it costs O(h), the tree's height, not O(n).
Height depends on shape. Inserting nums = [7, 1, 5, 3, 6] in that order chains the nodes four levels deep. Building from the sorted values, [1, 3, 5, 6, 7], with each middle value as a root keeps the tree balanced: 5 at the root, 3 and 7 as its children, and 1 and 6 below them. A balanced tree has height about log₂ n.
Search the balanced tree for 6. At 5, 6 > 5, so 6 can only be on the right, and 3 and 1 are discarded without a look. At 7, 6 < 7, so go left, and 6 is found. That is three comparisons for five nodes; a million balanced nodes would need about 20.
6 > 5 discards 5's whole left subtree, 1 and 3, unread; then 6 < 7 turns left onto 6.- Open lesson
Binary Search
A BST is binary search frozen into a tree. Each step down discards one side.
Case Scenario
The problem
Lowest Common Ancestor of a BST
Given a BST and two of its nodes p and q, return their lowest common ancestor. Walk from the root: both smaller → go left, both larger → go right, otherwise this node is the split. Tests list p and q by value; your function receives the nodes.
- Input
- root = [6, 2, 8, 0, 4, 7, 9, None, None, 3, 5], p = 3, q = 5
- Output
- 4
Lowest Common Ancestor of a BST gives two values, p and q, and asks for the deepest node with both in its subtree. The invariant points the way: while both values are smaller than a node, the answer is to its left; while both are larger, to its right. The first node where they split, or that equals one of them, is the answer: 4 for p = 3 and q = 5.
The direct approach ignores the ordering and searches like any binary tree: look for p and q in both subtrees of every node, and return the node where they turn up on different sides. That visits up to all n nodes, even though each comparison with a node's value already says which side both targets are on.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.