Binary Search Trees (BSTs) are special because they allow us to make decisions without exploring every node. This problem is a great example of taking advantage of that property to find the Lowest Common Ancestor (LCA) in O(h)time instead of searching the entire tree.

Problem

Given a Binary Search Tree and two nodes p and q, return their Lowest Common Ancestor (LCA).

The Lowest Common Ancestor is the lowest node in the tree that has both p and q as descendants.

A node is considered a descendant of itself, so if one of the nodes is an ancestor of the other, that node is the answer.

Example 1

        5
      /   \
     3     8
    / \   / \
   1   4 7   9
    \
     2

p = 3
q = 8

Answer = 5

Since 3 is on the left of 5 and 8 is on the right, the first node where they split is 5.

Example 2

        5
      /   \
     3     8
    / \
   1   4

p = 3
q = 4

Answer = 3

One node (3) is already an ancestor of the other (4), so the answer is simply 3.

Key Observation

Unlike a normal binary tree, a BST guarantees:

• Every value in the left subtree is smaller.
• Every value in the right subtree is larger.

This lets us determine which direction to move simply by comparing values.

At every node, only three situations are possible.

Case 1: Both nodes are smaller

        10
       /
      5

p = 2
q = 7

Both values are less than 10, so both nodes must be somewhere in the left subtree.

curr = curr.left

Case 2: Both nodes are larger

      10
        \
         15

p = 12
q = 20

Both values are greater than 10, so both nodes must be in the right subtree.

curr = curr.right

Case 3: The nodes split

        10
       /  \
      5   15

p = 5
q = 15

One node is on the left and one is on the right.

This means the current node is the first place where their paths diverge, making it the Lowest Common Ancestor.

The same logic also covers the situation where the current node is equal to either p or q.

        10
       /
      5
       \
        7

p = 5
q = 7

Since 5 is an ancestor of 7, the answer is 5.

Algorithm

Start from the root.

While the current node exists:

• If both p and q are smaller than the current node, move left.
• Else if both are larger than the current node, move right.
• Otherwise, you've found the Lowest Common Ancestor.

Because the BST tells us exactly which direction to move, we never need to search both subtrees.

Solution

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        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

Dry Run

Consider:

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

p = 2
q = 8

Step 1

Current node = 6

• 2 < 6
• 8 > 6

The nodes are on different sides.

So we've already found the split point.

Answer = 6

Another example:

p = 2
q = 4

Current = 6

Both are smaller.

Move left.

curr = 2

Current = 2

One node is the current node itself.

We return 2.

Time Complexity

We only travel from the root down toward a leaf.

Time Complexity: O(h)

where h is the height of the tree.

• Balanced BST: O(log n)
• Worst-case (skewed BST): O(n)

Space Complexity

The solution is completely iterative.

No recursion or extra data structures are used.

Space Complexity: O(1)

Why This Works

The BST property eliminates half of the remaining search space at every step.

Instead of exploring both subtrees like we would in a normal binary tree, we always know exactly which direction to move.

The moment the two nodes no longer lie on the same side—or when the current node matches one of them—we've reached the first node common to both paths.

That's exactly what the Lowest Common Ancestor is.

Interview Tips

This is the standard interview solution.

Interviewers are testing whether you recognize that this is a BST, not just a binary tree.

A common mistake is writing the generic Binary Tree LCA solution (O(n)), which recursively searches both subtrees. While that solution is correct, it ignores the BST property and misses the intended optimization.

Whenever you see Binary Search Tree, always ask yourself:

"Can I use the BST ordering to avoid searching the whole tree?"

In this problem, the answer is yes, leading to a simple iterative solution with O(h) time and O(1) space.