Lowest Common Ancestor of a Binary Tree III

Problem

Each node has a parent pointer. Given two nodes p and q, return their lowest common ancestor.

Input / Output

• Input: two tree nodes p and q, each with a parent pointer.
• Output: the lowest node that is an ancestor of both.

Constraints

• Nodes are guaranteed to exist in the tree.

Example

• Analogous to finding the intersection node of two upward-linked lists that both end at the root.