Data Structures & Algorithms

BST Operations

9 min read

Opening scenario

Lowest Common Ancestor of a BST (LC 235): given a BST and two nodes p, q, return their lowest common ancestor. Follow-up you should expect: Binary Search Tree Iterator (LC 173) — next()/hasNext() returning values in ascending order with O(h) memory.

A binary search tree (BST) here has distinct keys, with smaller keys in each left subtree and larger keys in each right subtree. Both target nodes exist in the tree. Their lowest common ancestor (LCA) is the deepest node that is an ancestor of both, counting a node as its own ancestor. Write n for node count and h for tree height. Consider what a comparison with the current node tells you about both targets. LC numbers identify LeetCode problems.

Question progression

Q1 — LCA in a general binary tree is an O(n) recursion. Why is a BST cheaper?

Question: What does the BST ordering invariant let you decide without exploring subtrees?

In the full tutorial

  • Canonical Template
  • Complexity
  • Pattern Recognition Signals
  • Practice Set
  • Pitfalls
  • Variations
  • Closing: When to Reach for This

Glossary history

Click dotted jargon to save explanations here.