Find the Lowest Common Ancestor in a Binary Tree

Medium

Problem

Given a binary tree (not a BST) and two nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

Example 1

Input:  root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3

Example 2

Input:  same tree, p = 5, q = 4
Output: 5

Also asked as: lca · lowest common ancestor in a BST · Find LCA of 2 nodes in a BST · Find LCA of 2 nodes in a BST · Find LCA in a Binary tree

Test cases

Case 1

Input:    [3,5,1,6,2,0,8,null,null,7,4], 5, 1
Expected: 3

Case 2

Input:    [3,5,1,6,2,0,8,null,null,7,4], 5, 4
Expected: 5

Case 3

Input:    [1,2], 1, 2
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution2 approaches

1. Post-order recursion (general binary tree)

Time O(n)Space O(h)

Return the node where p is found on one side and q on the other; that split point is the LCA.

function lca(root, p, q) {
if (!root || root === p || root === q) return root;
const left = lca(root.left, p, q);
const right = lca(root.right, p, q);
if (left && right) return root;
return left || right;
}

2. BST short-cut

Time O(h)Space O(1)

In a BST, walk down: go left if both targets are smaller, right if both larger, else you are at the LCA.

function lcaBST(root, p, q) {
let n = root;
while (n) {
if (p.val < n.val && q.val < n.val) n = n.left;
else if (p.val > n.val && q.val > n.val) n = n.right;
else return n;
}
}