Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST) where all node values are unique, and two nodes from the tree p and q, return the lowest common ancestor (LCA) of the two nodes.

The lowest common ancestor between two nodes p and q is the lowest node in a tree T such that both p and q as descendants. The ancestor is allowed to be a descendant of itself.

The LCA of nodes 3 and 4 is 3, since a node can be a descendant of itself.

Approach

Use the BST property to walk down the tree. If both p and q are less than the current node, go left; if both are greater, go right. Otherwise, the current node is the split point and therefore the LCA. This also covers the case where one node is an ancestor of the other.

Why It Works

In a BST, all values in the left subtree are smaller and all values in the right subtree are larger. The first node where p and q fall into different sides (or one equals the current node) is the lowest node that has both as descendants, which is exactly the LCA.

Complexity

• Time: O(h) where h is tree height
• Space: O(1)

Reference Implementation (Python)

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        cur = root
        while cur:
            if p.val < cur.val and q.val < cur.val:
                cur = cur.left
            elif p.val > cur.val and q.val > cur.val:
                cur = cur.right
            else:
                return cur
        return root