p17 — Hints

Open one at a time.

Hint 1 — Notice the Title

Re-read the problem title: “Lowest Common Ancestor of a Binary Search Tree.” The word “Search” is the entire hint. What does the BST property let you do at each node that you couldn’t do in a general binary tree?

Hint 2 — Where Do p and q Live?

At any node N:

• If p.val < N.val AND q.val < N.val, both p and q are in N’s left subtree. So N is an ancestor of both — but is it the lowest one? No: their LCA is deeper, in the left subtree.
• Symmetric for both > N.val.
• Otherwise, p and q are on different sides of N (or one IS N), so N IS their LCA.

Code this branching logic.

Hint 3 — Pseudocode

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

That’s the whole solution. 6 lines. Verify by tracing through the LC example [6,2,8,0,4,7,9,null,null,3,5] with p=2, q=8.

Hint 4 — Iterative Version

The recursion is tail-recursive: the recursive call’s return value is returned directly with no extra work. That means it converts trivially to a loop, saving O(H) stack space.

node = root
while True:
    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

This is the form to ship. Memorize it.

Hint 5 — Why It Works (the proof)

The LCA of p and q is by definition the deepest node having both as descendants. Any node strictly above the LCA also has both as descendants (less deep). Any node strictly below the LCA has at most one of them.

Walking down from the root:

• If both targets are in the left subtree, the current node has both as descendants — but a deeper node (somewhere in the left subtree) also does. So descend.
• Symmetric for right.
• Otherwise, the targets split. The current node has both as descendants (p on one side, q on the other). No deeper single node has both — because they’re in different subtrees. So this is the LCA.

This is the split-point argument. Internalize it; it generalizes to range queries on segment trees and B-trees.