Lowest Common Ancestor of a Binary Tree

Tree
DFS
Recursion

Given a binary tree and two node values p and q, return the value of their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Examples

Example 1

Input

root

p5

q1

Output

3

Example 2

Input

root

p5

q4

Output

5

Constraints

The number of nodes in the tree is in the range [2, 10⁴].
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique.
p ≠ q
p and q will exist in the tree.

Stuck? Hint 1

Recurse left and right; if both return non-null, the current node is the LCA.

Input

p5

q1

Expected Output

Ctrl / ⌘ + Enter

Lowest Common Ancestor of a Binary Tree

Tree
DFS
Recursion

Given a binary tree and two node values p and q, return the value of their lowest common ancestor (LCA) — the deepest node that has both p and q as descendants (a node can be a descendant of itself).

Examples

Example 1

Input

root

p5

q1

Output

3

Example 2

Input

root

p5

q4

Output

5

Constraints

The number of nodes in the tree is in the range [2, 10⁴].
-10⁹ ≤ Node.val ≤ 10⁹
All Node.val are unique.
p ≠ q
p and q will exist in the tree.

Stuck? Hint 1

Recurse left and right; if both return non-null, the current node is the LCA.

Input

p5

q1

Expected Output

Ctrl / ⌘ + Enter