Lowest Common Ancestor in a Binary Tree

Difficulty: Hard · Pattern: Tree DFS · Concept: Algorithms & Data Structures — Core Data Structures

Given a general binary tree (not necessarily a BST — no ordering to exploit) and the values of two nodes p and q known to exist in it, find their lowest common ancestor: the deepest node that has both p and q somewhere in its subtree (a node counts as its own ancestor, so if p is itself an ancestor of q, the LCA is p).

Your task: implement lowest_common_ancestor(root, p_val, q_val), returning the TreeNode (not just the value) that is the LCA. Assume all values in the tree are unique.

Implement it yourself

assert lowest_common_ancestor(tree, 4, 5).val == 2
assert lowest_common_ancestor(tree, 4, 3).val == 1
assert lowest_common_ancestor(tree, 6, 7).val == 6
assert lowest_common_ancestor(tree, 7, 3).val == 3
assert lowest_common_ancestor(tree, 2, 6).val == 1

Next: Three Sum to Zero (a harder variant of Pair With Target Sum)