Lowest Common Ancestor of a Binary Search Tree

A general binary tree needs a full traversal to find an LCA, but a BST’s ordering lets it be found by comparing values alone: at every node, both p and q being on the same side tells you which way to go, and them straddling the current node (or one equalling it) means you have arrived.

Recursive (BST property)

Time O(h)Space O(h)

If both target values are less than the current node, the LCA must be in the left subtree. If both are greater, it must be in the right subtree. Otherwise the current node is exactly where the two paths diverge (or one target is the current node) — that is the LCA.

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:
        if p.val < root.val and q.val < root.val:
            return self.lowestCommonAncestor(root.left, p, q)
        if p.val > root.val and q.val > root.val:
            return self.lowestCommonAncestor(root.right, p, q)
        return root

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

1 / 2

comparingresultdiscarded

At 6: p=2 is less than 6, but q=8 is greater than 6 -- they are on opposite sides, so 6 is the split point.

Complexity: the walk follows a single downward path from root to the LCA, never branching → O(h) time, where h is the tree height (O(log n) for a balanced BST, O(n) skewed). Recursion depth matches → O(h) space.

Iterative

OptimalTime O(h)Space O(1)

The recursion above is tail recursion — at each step it just moves to a child and repeats. That translates directly into a loop with no extra stack frames.

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

Why prefer this: identical O(h) time, but no call stack is used at all → O(1) space, an improvement over the recursive version’s O(h) stack, which matters on a very deep, unbalanced BST.