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

Lowest Common Ancestor of a Binary Tree

Medium TreeBinary TreeDFS LeetCode

Given a binary tree and two node values p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that has both p and q as descendants. A node can be a descendant of itself. Unlike BST, no ordering property is available here, so a general recursive approach is needed.

Example 1:

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
Sample Input
—
Sample Output
—
Constraints
  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique
Test Cases
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

Approach: Recursive DFS

If the current node is null or matches p or q, return it. Recurse into left and right subtrees. If both return non-null, the current node is the LCA (p and q are in different subtrees). Otherwise, return whichever side is non-null.

function lowestCommonAncestorOfABinaryTree(root, p, q) {
  function dfs(node) {
    if (!node || node.val === p || node.val === q) return node;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (left && right) return node;
    return left || right;
  }
  const result = dfs(root);
  return result ? result.val : -1;
}

Time Complexity: O(n)

Space Complexity: O(h)

Saved in this browser only. Private to you.

JavaScript