Find the Lowest Common Ancestor in a Binary Tree
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
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; }}