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

Read every interview problem free. Ten rooms need no account. A token opens a problem in full — Pro never counts.