Lowest Common Ancestor of a Binary Tree II

medium tree dfs lca

Problem

Given the root of a binary tree and two values p and q, return the lowest common ancestor (LCA) of the nodes holding those values. The LCA is the deepest node that has both targets in its subtree (a node may be its own ancestor).

Unlike the classic version, here p or q may not exist in the tree. If either is missing, there is no valid LCA and you must return null.

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

Outputnull

Value 4 is not in the tree, so no common ancestor exists. With p = 5, q = 1 the answer would be 3.

level-order (use "null" for missing children)

def lowest_common_ancestor(root, p, q):
    ans = None
    def dfs(node):
        nonlocal ans
        if not node:
            return False
        left = dfs(node.left)
        right = dfs(node.right)
        mid = node.val == p or node.val == q
        if mid + left + right >= 2 and ans is None:
            ans = node
        return mid or left or right
    dfs(root)
    return ans

function lowestCommonAncestor(root, p, q) {
  let ans = null;
  function dfs(node) {
    if (!node) return false;
    const left = dfs(node.left);
    const right = dfs(node.right);
    const mid = node.val === p || node.val === q;
    if (mid + left + right >= 2 && ans === null) ans = node;
    return mid || left || right;
  }
  dfs(root);
  return ans;
}

class Solution {
    private TreeNode ans = null;
    public TreeNode lowestCommonAncestor(TreeNode root, int p, int q) {
        dfs(root, p, q);
        return ans;
    }
    private boolean dfs(TreeNode node, int p, int q) {
        if (node == null) return false;
        boolean left = dfs(node.left, p, q);
        boolean right = dfs(node.right, p, q);
        boolean mid = node.val == p || node.val == q;
        if ((mid ? 1 : 0) + (left ? 1 : 0) + (right ? 1 : 0) >= 2 && ans == null) ans = node;
        return mid || left || right;
    }
}

TreeNode* ans = nullptr;
bool dfs(TreeNode* node, int p, int q) {
    if (!node) return false;
    bool left = dfs(node->left, p, q);
    bool right = dfs(node->right, p, q);
    bool mid = node->val == p || node->val == q;
    if (mid + left + right >= 2 && ans == nullptr) ans = node;
    return mid || left || right;
}
TreeNode* lowestCommonAncestor(TreeNode* root, int p, int q) {
    dfs(root, p, q);
    return ans;
}

Explanation

The key idea is a post-order DFS that, for every node, reports back whether the subtree rooted there contains either target. We compute this for the left child and the right child first, then check the node itself.

At each node we have three booleans: left (a target is in the left subtree), right (one is in the right subtree), and mid (this node itself is a target). If at least two of these are true, this node is the lowest node containing both targets — it is the LCA.

Because the traversal is bottom-up, the first node to satisfy the "two or more" condition is the deepest such node, so we record it once and never overwrite it.

The missing-node twist (LCA II): if only one target exists, no node will ever see two hits, so ans stays null — exactly the required behavior. We do not need a separate existence pass; the count naturally guards against it.

Example on [3,5,1,6,2,0,8] with p = 5, q = 4: the DFS finds 5 but never finds 4, so no node reaches a count of two and the answer is null.

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