Lowest Common Ancestor of a BST

Signal

"Lowest common ancestor" in a BST specifically means the ordering property does the searching for you — you don't need to search both subtrees blindly like you would on a general binary tree.

Approach

Start at the root and walk down: if both p.val and q.val are less than the current node's value, the split (if any) must be to the left, so go left; if both are greater, go right; otherwise the values straddle the current node (or one of them is the current node) — that's the LCA.

Skeleton

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

Solution

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def lowest_common_ancestor(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
    return None

Complexity

O(h) time, h = tree height (O(log n) balanced, O(n) skewed) — one path down, no backtracking. O(1) space iteratively.

Pitfalls

• This shortcut relies entirely on the BST ordering property — on a general binary tree you'd need to search both subtrees for p and q and combine the results, which is a different (and pricier) algorithm.
• If p or q is the current node, that node is the LCA — the else branch above already covers this alongside the straddling case, so no separate check is needed.