LCA in a BST Explained: Finding LCA for 2, 8 and 2, 4 in [6,2,8,0,4,7,9]

Imagine you are handed the binary search tree $[6,2,8,0,4,7,9]$ and asked to find the Lowest Common Ancestor (LCA) for two targets: first, $p=2$ and $q=8$, and second, $p=2$ and $q=4$. In a generic binary tree without ordering guarantees, finding where two nodes meet requires scanning the entire structure or recording full root-to-node paths for both targets and comparing them element by element.

That brute-force path-comparison approach works, but it ignores a massive structural advantage. Because this tree is a Binary Search Tree (BST), every node to the left is strictly smaller than the parent, and every node to the right is strictly larger. If you treat the BST like a standard unordered binary tree, you waste valuable traversal steps wandering down branches that have no mathematical bearing on where $p$ and $q$ diverge.

Without an ordered traversal strategy, locating the divergence point between 2 and 8 forces you to traverse blindly across both halves of the tree before figuring out they sit on opposite sides of the root 6. We need a method that exploits the strict ordering rules of BSTs to pinpoint the split instantly.

To understand how to find the Lowest Common Ancestor without wandering through the entire tree, we return to our locked example: the BST $[6,2,8,0,4,7,9]$. In this tree, 6 sits at the root, its left subtree contains values strictly smaller than 6 ($\{0,2,4\}$), and its right subtree contains values strictly larger ($\{7,8,9\}$).

When searching for $\text{LCA}(2,8)$, our target nodes 2 and 8 lie on opposite sides of the root value 6. Node 2 is smaller than 6, and node 8 is larger. This divergence point at the root is precisely what makes 6 the lowest common ancestor.

By contrast, when searching for $\text{LCA}(2,4)$, both target nodes are smaller than the root 6. They both live in the left subtree. Therefore, the root 6 cannot be the divergence point; we must step left to examine the subtree rooted at 2.

6 <-- LCA(2, 8)
/ \
2 8
/ \
0 4 <-- LCA(2, 4)

This reveals a strict three-way directional logic at any current node during our traversal. If both target values are smaller than the current node, move left. If both are larger, move right. The exact moment this rule fails—where one target is $\le$ and the other is $\ge$, or when we land directly on one of the targets—is our LCA.

Try this: Given currentNode = 6, p = 2, q = 4:

To see the decision map in action, we will trace two distinct queries on our canonical Binary Search Tree: $BST=[6,2,8,0,4,7,9]$. The structure of this tree places 6 at the root, with left subtree rooted at 2 (having children 0 and 4) and right subtree rooted at 8 (having children 7 and 9). We want to find the Lowest Common Ancestor for $p=2$ and $q=8$, and then for $p=2$ and $q=4$.

Given:
- Root node: 6
- Left subtree: [2, 0, 4], Right subtree: [8, 7, 9]
- Query 1: $p=2$, $q=8$
- Query 2: $p=2$, $q=4$

Steps for Query 1: LCA(2, 8)
1. Start at Root (6): Compare $p.val=2$ and $q.val=8$ with current node value 6. Since $2<6$ and $8>6$, the values sit on opposite sides of the root. The split happens right here.
2. Result for Query 1: Return node 6 as the LCA because it is the exact divergence point.

Steps for Query 2: LCA(2, 4)
1. Start at Root (6): Compare $p.val=2$ and $q.val=4$ with current node value 6. Both values are strictly less than 6 ($2<6$ and $4<6$). Take the left branch to node 2.
2. At Node (2): Compare $p.val=2$ and $q.val=4$ with current node value 2. Here, $p.val=2$ equals the current node value, while $q.val=4$ is greater than 2. Because they no longer share the same direction (one is equal, one is greater), we have found our split point.
3. Result for Query 2: Return node 2 as the LCA. Notice that node 2 is an ancestor of node 4, satisfying the BST LCA rule where a node can be the ancestor of another.

Try this: Given the BST [6, 2, 8, 0, 4, 7, 9], trace the exact node visits and comparisons when finding LCA(4, 9). Which node triggers the split condition?

Now that you have seen how 6 splits 2 and 8 and how 2 acts as an ancestor for 4 in the BST $[6,2,8,0,4,7,9]$, let's test your ability to execute this mental model on a slightly different pair.

Imagine you are asked to find the Lowest Common Ancestor for $p=0$ and $q=4$ within this same BST. Recall that 0 and 4 reside in the left subtree rooted at 2. Without writing any code, trace the comparison steps starting from the root node 6, determine which node causes the search paths of 0 and 4 to diverge, and identify the final returned LCA node.

Take a moment to mentally evaluate the comparisons at the root 6 and the left child 2, then check your reasoning against the structural layout of the tree.

Try this: Given the BST [6, 2, 8, 0, 4, 7, 9], what is the step-by-step path and final returned node for LCA(0, 4)?

We started with our BST $[6,2,8,0,4,7,9]$ where LCA(2, 8) split at the root 6, and LCA(2, 4) terminated early at node 2 because 2 was an ancestor of 4. The core pattern we extracted is that the LCA is always the first node whose value falls inclusively between $p\text{.val}$ and $q\text{.val}$. Now, let us apply this exact mechanism to a new scenario where the BST shape is distorted.

Imagine our BST is modified so that the left subtree of 2 is completely missing, and node 4 is attached directly as the left child of 6, making the tree skewed. If we want to find $\text{LCA}(0,4)$ in this modified tree, our directional decision rule remains identical. We start at root 6. Since both 0 and 4 are less than 6, we move left to node 2. At node 2, 0 is less than 2, but 4 is greater than 2. The path diverges right here, meaning node 2 is our split point and thus our LCA.

The real power of this logic is that its time complexity remains $O(h)$ where $h$ is the tree height, and space complexity drops to $O(1)$ if implemented iteratively. Whether the tree is balanced like our initial $[6,2,8,0,4,7,9]$ layout or skewed, the comparison map never changes because the BST invariant guarantees that all values in the left subtree are smaller and all values in the right subtree are larger.

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