Lowest Common Ancestor of a Binary Tree Medium 0 attempts
LeetCode ↗

Lowest Common Ancestor of a Binary Tree

Medium TreeBinary TreeDFS LeetCode

You're given the root of a binary tree and two distinct node values p and q, both guaranteed to exist in a tree with unique values. Return the ancestor’s value. Find their lowest common ancestor (LCA) — the deepest node in the tree that has both p and q among its descendants, where a node is allowed to be a descendant of itself. The tree has no BST-style ordering to exploit here, so this calls for a general tree traversal rather than value comparisons.

Input Format
Implement lowestCommonAncestorOfABinaryTree(root, p, q). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
root = [3,5,1,6,2,0,8,null,null,7,4]
p = 5
q = 4
Output
5
Constraints
  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique
Test Cases (2)
Case 1
Args: [[3,5,1,6,2,0,8,null,null,7,4],5,1] Expected: 3
Case 2
Args: [[3,5,1,6,2,0,8,null,null,7,4],5,4] Expected: 5
Topics
TreeBinary TreeDFS

Parent Map

Record each node’s parent. Mark all ancestors of p, then walk from q toward the root until the first marked ancestor is reached.

javascript
function lowestCommonAncestorOfABinaryTree(root, p, q) {
  const parent=new Map([[root,null]]),stack=[root];let pn,qn;
  while(stack.length){const node=stack.pop();if(node.val===p)pn=node;if(node.val===q)qn=node;for(const child of [node.left,node.right])if(child){parent.set(child,node);stack.push(child);}}
  const ancestors=new Set();while(pn){ancestors.add(pn);pn=parent.get(pn);}
  while(!ancestors.has(qn))qn=parent.get(qn);
  return qn.val;
}

Time: O(n) | Space: O(n) auxiliary space, excluding output

Saved in this browser only. Private to you.

JavaScript