Lowest Common Ancestor Of A BST#

Problem#

Given a binary search tree and two nodes p and q present in it, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as a descendant of itself).

Example#

In a BST rooted at 6 with the standard layout [6, 2, 8, 0, 4, 7, 9, 3, 5], the LCA of 2 and 8 is 6, and the LCA of 2 and 4 is 2.

Optimal approach#

A general-tree LCA needs to search both subtrees, but a BST lets you use its ordering. Start at the root. If both p and q are greater than the current node, the ancestor must be in the right subtree, so go right. If both are smaller, go left. The first node where the two values split (one is less and the other is greater, or one equals the current node) is the lowest common ancestor. You only ever walk one path from root toward the leaves.

Solution#

 1class TreeNode:
 2    def __init__(self, val=0, left=None, right=None):
 3        self.val = val
 4        self.left = left
 5        self.right = right
 6
 7
 8def lowest_common_ancestor(root, p, q):
 9    node = root
10    while node:
11        if p.val > node.val and q.val > node.val:
12            node = node.right
13        elif p.val < node.val and q.val < node.val:
14            node = node.left
15        else:
16            return node
17    return None
18
19
20root = TreeNode(6,
21    TreeNode(2, TreeNode(0), TreeNode(4, TreeNode(3), TreeNode(5))),
22    TreeNode(8, TreeNode(7), TreeNode(9)))
23print(lowest_common_ancestor(root, root.left, root.right).val)        # 6
24print(lowest_common_ancestor(root, root.left, root.left.right).val)   # 2

Complexity#

• Time: O(h), one downward path, where h is the tree height.
• Space: O(1) for the iterative walk.

More BST problems live in the trees topic. Keep going with the 60-day challenge.