LCA in BT

Hard

The node where the two searches meet

Problem

Return the lowest common ancestor of two nodes in a binary tree.

In simple words

Recurse; the node where the two targets first appear in different subtrees is their lowest common ancestor.

The idea

Recurse into both subtrees looking for either target. A node that finds one target on each side is the lowest common ancestor; a node that finds results on only one side simply passes that result up.

The trick

Return the node itself when it matches either target.
Both sides non-null means you are standing on the answer.
O(n) single pass, no parent pointers needed.

←→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.