p17 — Lowest Common Ancestor of a Binary Search Tree

Source: LeetCode 235 · Medium (Easy if you spot the BST shortcut) · Topics: Tree, DFS, BST Companies (2024–2025 frequency): Amazon (high), Meta (high), Microsoft (high), LinkedIn (very high — phone screen staple), Google (medium), Bloomberg (medium) Loop position: phone-screen or first round; almost always paired with LC 236 (general LCA) as the explicit follow-up.

1. Quick Context

LCA-of-BST is the cleanest demonstration of the BST property as algorithmic lever. The general LCA problem (LC 236) for an arbitrary binary tree requires post-order traversal with a 4-case logic and is O(N). The BST version collapses to a single-pass O(H) walk:

At the current node, if both targets p and q lie in the left subtree (p.val < node.val and q.val < node.val), recurse left. If both lie in the right subtree, recurse right. Otherwise, the targets are on opposite sides (or one is this node), so this node IS the LCA — return it.

That’s it. The whole solution is 6 lines. The interview-grade discussion is:

• Why this works (the split-point argument: the LCA is exactly the first node where p and q diverge in the BST search path).
• How it compares with the general LCA (LC 236) — a comparison interviewers explicitly ask for.
• The pitfall: assuming p.val < q.val (some problem variants do; LC 235 does not).
• The iterative form (no recursion, O(1) auxiliary space — yes, truly O(1)).

What it looks like it tests: can you traverse a tree. What it actually tests: can you recognize when an extra data-structure invariant turns an O(N) problem into O(log N) — the kind of pattern recognition that separates Senior+ engineers.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

STOP. 6-min timer. If you find yourself writing a “search for p, search for q, intersect paths” solution — STOP and re-read the problem title. Why does it say “of a Binary Search Tree” specifically?

3. Prerequisite Concepts

• p16 — the BST invariant
• Standard recursive tree walks (return a node from recursion)
• The concept of an “LCA” — for any two nodes p and q in a tree, the LCA is the deepest node that has both as descendants (a node is its own descendant)
• Iterative tree descent (the BST “search” pattern, see phase-01-foundations/labs/lab-09-tree-traversal-fundamentals.md)

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given a BST and two nodes p and q present in it, return their lowest common ancestor (the deepest node that has both as descendants; a node is considered a descendant of itself).”

Step 2 — Clarify:

• “Are p and q guaranteed to exist in the tree?” (LC: yes.)
• “Can p == q?” (LC: no — they are distinct.)
• “Can p be an ancestor of q?” (Yes — then p is the LCA. State this; don’t trip on it.)
• “Are values guaranteed unique?” (LC: yes — node values are unique. State this; the algorithm relies on it.)

Step 3 — Constraints: N up to 10^5. BST may be unbalanced. Need O(H) — average O(log N), worst O(N).

Step 4 — Examples:

• Tree [6,2,8,0,4,7,9,null,null,3,5], p=2, q=8 → 6 (split at root).
• Same tree, p=2, q=4 → 2 (p is ancestor of q).
• Same tree, p=3, q=5 → 4 (split in subtree).
• Two-node tree [1,null,2], p=1, q=2 → 1 (ancestor case).

Step 5 — Brute Force: Find path from root to p, find path from root to q, return last common node. O(N) time, O(N) space (paths). Mention this then immediately optimize using the BST property.

Step 6 — Complexity (optimal): O(H) time = O(log N) average, O(N) worst (skewed). O(1) auxiliary space iteratively; O(H) stack space recursively.

Step 7 — Pattern Recognition: “An ordered tree where I’m searching for the split point of two queries” → descend until divergence. This pattern reappears in LC 270 (Closest BST Value), LC 285 (Inorder Successor), and segment-tree range queries.

Step 8 — Develop optimal:

• Recursive:

  def lca(node, p, q):
      if p.val < node.val and q.val < node.val:
          return lca(node.left, p, q)
      if p.val > node.val and q.val > node.val:
          return lca(node.right, p, q)
      return node
  

• Iterative (preferred for production): same logic in a while True loop, no recursion, true O(1) space.

Step 9 — Prove correctness: The LCA is by definition the deepest node N such that p and q are both in N’s subtree. Walking down from the root:

• If both p.val and q.val < N.val, then both are in N’s left subtree — N is an ancestor but not the lowest, so descend left.
• Symmetric for both >.
• Otherwise (split: one ≤ and one ≥, OR one of them equals N.val), then N is the first node where the BST search path for p and the path for q diverge. Any deeper node would lose one of the two. Therefore N is the LCA. ∎

5. Progressive Hints

If stuck for 6 min, open hints.md.

6. Deeper Insight — The “split-point” framing

Conceptually, the LCA of two nodes in a BST is the first divergence in their search paths. If you started two parallel BST searches at the root — one looking for p, one looking for q — they would walk in lockstep down identical prefixes (because the BST search decision at each node is purely based on the value being searched for), and the first node where one would turn left and the other right is exactly the LCA.

This framing generalizes:

• LC 270 (Closest Value in BST): descend, tracking the closest value seen. Same single-pass O(H) walk.
• LC 272 (Closest K Values in BST): combine descent with inorder around the split point.
• Range queries on a segment tree: walk down, splitting where the range diverges (left subrange vs right subrange).

This “split-point descent” is one of the most reusable tree templates. Internalize it.

7. Anti-Pattern Analysis

1. Searching for p and q separately, then intersecting paths. O(N) time and O(N) space — correct, but discards the BST property. State as brute force; do not ship it.
2. Forgetting the equality case (p is an ancestor of q). The pseudocode if p.val < node.val and q.val < node.val handles this correctly because when p.val == node.val, both conditions are false and we return node. Beginners sometimes write <= and break this. Always use strict <.
3. Assuming p.val < q.val. Some textbook variants order them; LC 235 does not. Always write the algorithm symmetric in p and q.
4. Calling lca(node, p, q) recursively when iteration would do. Recursion is fine but adds O(H) stack. For interview, iterative is the preferred form because it demonstrates you understand “the recursion is tail-recursive — eliminate it.”
5. Returning the LCA’s value instead of the node. Read the signature carefully. LC returns the TreeNode.

8. Skills & Takeaways

• Recognize when invariants collapse complexity. BSTs let LCA drop from O(N) to O(H). Identifying which property is doing the work is a Senior-level skill.
• Compare-and-contrast with the general case. Any time the problem says “Binary Search Tree” instead of “binary tree,” ask: what does the search property let me skip?
• Tail-recursion elimination. The recursive solution is tail-recursive; converting it to a while loop is the production-quality move.
• Path-divergence as a template. This shows up in segment trees, B-tree range queries, and trie-based prefix problems.

9. When to Move On

Move on when:

• You can write both the recursive and iterative solutions from memory in <3 minutes each.
• You can explain — without code — why the BST property reduces the problem from O(N) to O(H).
• You can sketch the general LCA solution (LC 236) and articulate which 4 cases the post-order recursion handles.
• Your stress test confirms agreement with a brute-force path-intersection oracle on 1000 random BSTs.

10. Company Context

LinkedIn:

• This is a flagship phone screen problem at LinkedIn. Expect the follow-up “now do it for a general binary tree” (LC 236) in the same 45-minute slot.
• Bonus: “what if we have many queries on the same tree?” → preprocess for O(log N) per query via Euler tour + RMQ; mention but don’t implement.
• Scorecard phrase: “Algorithm — used BST property; produced iterative form; articulated LCA generalization.”

Amazon:

• Standard SDE-II ask. Look for “what if the tree is a billion nodes on disk?” → discuss B-tree LCA (same split-point logic, just on a fan-out > 2 node).
• Scorecard phrase: “Deep Dive — applied invariant to achieve O(H); extended to B-tree case.”

Meta:

• Often used as a warm-up before LC 236. If you solve LC 235 in 5 minutes, expect LC 236 as the real problem.
• Scorecard phrase: “Coding Excellence — clean 6-line solution; smooth transition to general case.”

Google:

• Will push on proof: “prove this is correct” (give the split-point argument). Also: “what’s H in the worst case?” (N for a skewed tree — the BST guarantee is average O(log N), not worst).
• Scorecard phrase: “Algorithm — correctness proof; honest about worst-case degradation.”

Microsoft:

• Often asks the iterative variant first. Will probe: “what’s the space complexity if I use recursion?” → O(H) for the stack.
• Scorecard phrase: “Problem Solving — recognized tail-recursive structure; converted to loop.”

Bloomberg:

• Uses this in the context of “find the common parent in an org-hierarchy BST keyed by employee ID.” Be ready for domain framing.
• Scorecard phrase: “Strong — clean solution; understood real-world use.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4 / SDE-II):

• Writes the recursive solution after a hint about the BST property.
• Mentions iterative form when asked.
• Handles p ancestor of q correctly with one trace.

Senior (L5 / SDE-III):

• Writes iterative form first try (it’s the natural choice once you see the split-point).
• Articulates split-point argument verbally.
• Sketches LC 236 when asked, identifies the 4 cases.

Staff (L6):

• States the BST shortcut before touching keys, frames it as “invariant collapses complexity.”
• Discusses worst-case H = N and references AVL/RB-trees for guarantees.
• Sketches Euler-tour + RMQ for multi-query preprocessing.

Principal (L7+):

• Generalizes split-point descent to B-trees, LSM-tree level traversal, range queries on segment trees.
• Discusses concurrent LCA queries on a shared BST (snapshot isolation, COW).
• Identifies the meta-pattern: ordered structures let queries collapse from O(N) to O(log N) via dichotomy.

13. Follow-up Q&A

Q1: Implement LCA for a general binary tree (LC 236). A: Post-order recursion. lca(node, p, q): if node is None or node == p or node == q, return node. Recurse left and right. If both return non-None, this node IS the LCA. Otherwise return the one non-None side (propagating the found target up). O(N) time, O(H) stack.

Q2: What if we have Q queries on the same tree? A: Preprocess with Euler tour + sparse-table RMQ → O(N log N) preprocessing, O(1) per query. Mention; don’t implement unless explicitly asked.

Q3: What if the tree might not contain p or q? A: Modify the general LCA to track whether both were found. Return (node, count_found). Only return the node if count_found == 2. Otherwise return None.

Q4: What if the tree is stored on disk and each node access costs an I/O? A: The BST descent makes O(H) I/Os = O(log N) for balanced. For worst-case guarantees, switch to a B-tree (each node has many children → much shallower tree → fewer I/Os). The split-point algorithm generalizes naturally: at a B-tree node, find the first child whose key range contains either p or q; if p and q fall in the same child, descend; otherwise return this B-tree node as LCA.

Q5: How would you parallelize LCA queries across many (p_i, q_i) pairs on the same tree? A: For independent reads on an immutable BST, trivially parallel (each query is its own descent). For an updated BST, use snapshot isolation (COW) or a multi-versioned BST. For mass queries with locality, batch the queries that share a common prefix (offline LCA = Tarjan’s algorithm, O((N + Q) α(N)) with DSU).

14. Solution Walkthrough

See solution.py:

• lca_recursive(root, p, q) — the 6-line recursive form.
• lca_iterative(root, p, q) — the production form, true O(1) auxiliary space.
• lca_general_recursive(root, p, q) — LC 236 reference for the canonical follow-up.
• lca_path_intersect(root, p, q) — O(N) brute force used as stress-test oracle.
• stress_test() — generates 1000 random BSTs with random (p, q) pairs; asserts all 4 implementations agree.
• edge_cases() — p == root, p ancestor of q, two-node tree, deep skewed tree.

Run: python3 solution.py → “ALL TESTS PASSED” on stdout.

15. Beyond the Problem

Principal-engineer code review comment:

“Fine for the BST case but please add a doc-comment that names the precondition explicitly: this assumes (a) p and q are both present in the tree and (b) node values are unique. Both are easy for the caller to violate and the failure mode is a wrong answer, not a crash — the worst kind of bug. Also, prefer the iterative form here: the recursion is tail-recursive and the iterative form is 2 extra lines for O(1) space and zero risk of stack overflow on adversarial skewed inputs. If we ever reuse this in a context where the tree might be malformed (depth > 10^4 from a sorted-insert build), the recursive form will throw, and the stack trace will name the wrong subsystem because Python’s recursion-limit error is generic. Save a future on-call from a 2 a.m. page — write the loop.”

Connections forward:

• p18 (Kth Smallest BST) uses the same “descend the BST exploiting order” framing.
• LC 236 (general LCA) is the explicit follow-up — drill it.
• Phase 3 segment-tree range queries use the same split-point descent.
• Tarjan’s offline LCA (DSU-based) is the next layer up; mentions appear in graph theory rounds at Google/research orgs.