Lowest Common Ancestor of a Binary Tree

medium tree dfs recursion

Problem

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Inputtree = [3,5,1,6,2,0,8], p = 5, q = 1

Output3

5 and 1 are siblings under 3.

tree (level-order)

def lowest_common_ancestor(root, p, q):
    if root is None or root.val == p or root.val == q:
        return root
    l = lowest_common_ancestor(root.left, p, q)
    r = lowest_common_ancestor(root.right, p, q)
    if l and r: return root
    return l or r

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, int p, int q) {
        if (root == null || root.val == p || root.val == q) return root;
        TreeNode l = lowestCommonAncestor(root.left, p, q);
        TreeNode r = lowestCommonAncestor(root.right, p, q);
        if (l != null && r != null) return root;
        return l != null ? l : r;
    }
}

TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
    if (!root || root->val == p || root->val == q) return root;
    TreeNode* l = lowestCommonAncestor(root->left, p, q);
    TreeNode* r = lowestCommonAncestor(root->right, p, q);
    if (l && r) return root;
    return l ? l : r;
}

Explanation

This is a plain binary tree with no sorting to exploit, so we lean on a single bottom-up DFS. Each call answers one question: "did I find p or q somewhere in my subtree, and if so where?"

The base case is the key idea. If the current node is null, or it is one of the targets, we return it immediately. Finding a target stops the search at that point.

For an internal node we search both sides: l = recurse(left) and r = recurse(right). If both sides came back non-null, then p and q live in different subtrees, so the current node is the meeting point — the LCA — and we return it.

If only one side found something, we bubble that result up with return l or r. This carries the discovered node (or a deeper LCA) toward the root.

Example: tree [3,5,1,6,2,0,8] with p = 5, q = 1. Node 5 is found in the left subtree and 1 in the right, so at the root 3 both sides are non-null and the answer is 3.

Time: O(n) Space: O(h)