Lowest Common Ancestor of a BST — LC 235 O(h) Navigation Interview Guide

Problem Statement#

Given a Binary Search Tree (BST) and two of its nodes p and q, return their lowest common ancestor (LCA). A node can be a descendant of itself.

Constraints:

• Number of nodes is in range 2 to 100000
• All node values are unique
• Both p and q exist in the BST
• p is not equal to q

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6

Input:  root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2

Why This Problem Matters#

LeetCode 235 LCA of a Binary Search Tree is the BST-optimized variant of LC 236, asked frequently at Amazon, Meta, Microsoft, Google, and Apple. The interviewer is testing one specific signal: do you exploit data structure invariants instead of falling back to a generic algorithm?

Candidates who solve LC 235 with the LC 236 post-order DFS get the right answer but score poorly. The expected solution uses the BST ordering to navigate from root straight to the LCA in O(h) time and O(1) extra space — a clean reduction from the generic O(n) solution.

The problem also seeds intuition for related BST problems: range queries, finding the closest value, validating a BST, and binary lifting for ancestor queries. The "find where ranges split" mental model carries over directly.

The Core Insight#

In a BST, every node's left subtree holds values strictly less than itself and the right subtree holds strictly greater values. Given two target values p.val and q.val, the LCA is the first node we encounter walking down from the root where the targets fall on different sides (or one target equals the current node).

Three cases at each step:

1. Both p.val and q.val are less than node.val — both targets are in the left subtree, so move left.
2. Both p.val and q.val are greater than node.val — both targets are in the right subtree, so move right.
3. Otherwise — split point or current node equals a target — return current node.

This iterative descent uses no recursion stack, giving O(1) extra space and O(h) time, which is O(log n) on a balanced BST.

Visual Dry Run#

BST: 6 -> {2 -> {0, 4 -> {3, 5}}, 8 -> {7, 9}}, p = 2, q = 8.

For p = 2, q = 4:

The descent stops at the first node where the targets diverge or one matches.

Solution (Optimal)#

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left
            elif p.val > node.val and q.val > node.val:
                node = node.right
            else:
                return node
        return None

var lowestCommonAncestor = function(root, p, q) {
    let node = root;
    while (node) {
        if (p.val < node.val && q.val < node.val) {
            node = node.left;
        } else if (p.val > node.val && q.val > node.val) {
            node = node.right;
        } else {
            return node;
        }
    }
    return null;
};

Time: O(h) — at most one step per level; O(log n) balanced, O(n) skewed. Space: O(1) — iterative descent uses no recursion stack.

Common Mistakes#

• Using the generic LC 236 post-order DFS — correct answer but throws away the BST property
• Forgetting to handle the equal case — must return the current node when one target equals it
• Writing asymmetric conditions without normalizing p.val and q.val order — works only if both sides use strict comparisons
• Recursing instead of iterating — same time but uses O(h) stack space unnecessarily
• Returning node.val instead of the node itself — interview will dock for not reading the return type

Interview Tips#

• State the BST invariant before coding: "left subtree all less than, right subtree all greater than"
• Explicitly say you are choosing iteration over recursion to get O(1) space
• Mention that on a self-balanced BST (AVL, red-black), this is O(log n); on a skewed BST it degrades to O(n)
• The recursive variant is fine to mention but iterate by default

Follow-up Questions#

• LCA without BST property — solve LC 236 with post-order DFS
• LCA on a BST with parent pointers — walk up from both nodes, compare ancestor sets
• Distance between two nodes in a BST — find LCA, compute depths
• LCA queries on a BST that may be modified — use binary lifting or augment with subtree info

Key Takeaways#

• LeetCode 235 LCA of a BST is Medium and a top BST navigation problem at Amazon, Meta, Microsoft, Google, and Apple
• Time is O(h) which is O(log n) balanced; space is O(1) with iteration
• Pattern: walk down from root; go left if both targets are smaller, right if both are larger, else current node is the LCA
• The split point is where the two targets first diverge or one equals the current node
• Always exploit the BST property — never default to LC 236's post-order DFS on a known BST
• Iterative descent avoids the O(h) recursion stack required by the recursive version
• Same descent template extends to BST range queries, closest value, and floor/ceiling lookups