Lowest Common Ancestor

Medium

Where the two search paths split

In simple words

The meeting point of two nodes is the lowest node that has one on each side (or is one of them).

The idea

Recurse down; if a node is one of the targets, return it. If both left and right recursions return non-null, this node is the split point — the LCA.

←→stepspaceplay

1/5

Optimal

timeO(n)spaceO(h)

Split point of both paths.

1function lca(node, p, q) {2  if (!node || node === p || node === q) return node;3  const l = lca(node.left, p, q);4  const r = lca(node.right, p, q);5  return l && r ? node : (l ?? r);6}

Input

nodes: 6, 5 edges

Memory

left: —
right: —

Output

LCA: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [3,5,1,6,2,0,8], p = 5, q = 1
Output:: 3
Explanation:: 5 and 1 meet at the root 3.

Example 2

Input:: tree = [3,5,1,6,2,0,8], p = 6, q = 2
Output:: 5
Explanation:: 6 and 2 both sit under 5.

Example 3

Input:: tree = [1,2], p = 1, q = 2
Output:: 1
Explanation:: The root is their meeting point.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.