Medium · Trees

Lowest Common Ancestor of a Binary Tree III

Given two distinct nodes p and q of a binary tree whose nodes also carry parent pointers (the root is not passed in), return their lowest common ancestor: the deepest node that has both p and q in its subtree (a node is in its own subtree). The tests list the tree in level order and name p and q by their unique values.

Examples

Example 1

p=7, q=8 → 3

Output: LCA = 3

Example 2

p=6, q=4 → 5

Output: LCA = 5

Rebuild it in the studio

Open every published interview problem, solution, scene, and memory room free, with no account.