Lowest Common Ancestor of a Binary Tree

Problem Given a binary tree and two nodes p and q, return their Lowest Common Ancestor (LCA) — the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Input / Output

• Input: the tree root and two node references p, q.
• Output: the LCA node.

Constraints

• Both p and q are guaranteed to exist in the tree; node values are unique.
• Plain binary tree (not necessarily a BST); no parent pointers unless stated.

Example

      3
     / \
    5   1
   / \ / \
  6  2 0  8

• LCA(5, 1) = 3; LCA(5, 6) = 5.