Lowest Common Ancestor of a Binary Search Tree — Solution

Problem

Given a binary search tree and two nodes p and q, find the deepest node that is an ancestor of both. A node counts as its own ancestor, so if q is a descendant of p, the answer is p itself.

[6,2,8,0,4,7,9,null,null,3,5]

• Input: root = above BST, p = 2, q = 4
• Output: 2
• Explanation: Node 4 lives in node 2's right subtree, making 2 the lowest node that contains both.

Counter-example: if p = 2 and q = 8, the answer is 6 — not 2 — because 8 is entirely in the right subtree and the two targets diverge at the root.

Intuition

A BST's ordering property tells you exactly where the LCA must be at every step: if both targets are smaller than the current node, the LCA lives in the left subtree; if both are larger, it lives in the right subtree. The instant the two targets land on opposite sides of a node — or the current node matches one of them — you've reached the split point, which is the LCA.

Solution — Iterative BST Traversal

Walk down the tree one step at a time. At each node, compare both target values to the current value to decide which direction to go. Return the first node where the targets no longer agree on a direction.

1. Start at the root.
2. If both p.val and q.val are strictly less than node.val, move to the left child — the LCA must be smaller.
3. If both are strictly greater than node.val, move to the right child — the LCA must be larger.
4. Otherwise — the targets straddle the current node, or one of them equals it — return the current node.

1def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
2    node = root
3    while node:
4        if p.val < node.val and q.val < node.val:
5            node = node.left    # both targets are smaller — LCA is to the left
6        elif p.val > node.val and q.val > node.val:
7            node = node.right   # both targets are larger — LCA is to the right
8        else:
9            return node         # split point or exact match — this is the LCA

• Time: O(h) — one step taken per iteration, where h is the tree height; O(log n) for a balanced BST, O(n) worst case for a degenerate skewed tree.
• Space: O(1) — only a single pointer is maintained, no recursion stack.

Complexity Summary

Common Mistakes

• Applying this approach to a general binary tree: BST value comparisons only work because of the BST ordering guarantee. On an arbitrary binary tree you must use the general O(n) post-order DFS approach instead — this one silently produces wrong answers without that guarantee.
• Using <= or >= in the directional checks: The conditions must be strict (< and >). When p.val == node.val, neither branch should fire — the current node is the answer and the else must catch it.
• Assuming the smaller target is always the LCA: The LCA is the split-point, not the smaller value. For p = 0 and q = 4, the LCA is 2, not 0.
• Writing the recursive version and overlooking its stack cost: A recursive implementation of the same comparisons uses O(h) space due to the call stack. The iterative version shown here is strictly better in space.
• Forgetting that a node is its own ancestor: If p = 4 and q = 3 (where 3 is in 4's left subtree), the answer is 4. The else branch handles this because when node.val == p.val, neither strict-less nor strict-greater fires.

Related Problems

• lowest-common-ancestor-of-a-binary-tree — same goal on a general binary tree where you cannot use value comparisons and must visit every node
• search-in-a-binary-search-tree — the same left/right navigation pattern, just searching for a single target
• kth-smallest-element-in-a-bst — BST traversal using in-order ordering properties
• delete-node-in-a-bst — BST traversal that locates a target node using the same comparison logic
• binary-search — the same divide-and-eliminate-half idea applied to a sorted array instead of a BST