Lowest Common Ancestor of a Binary Tree IV

medium tree dfs lca

Problem

Given the root of a binary tree and an array of distinct node values nodes, return the lowest common ancestor of all of them — the deepest node whose subtree contains every node in the array.

All values in nodes are guaranteed to exist in the tree. A node can be its own ancestor, so the LCA may itself be one of the targets.

Inputroot = [3,5,1,6,2,0,8], nodes = [6,2,0]

Output3

6 and 2 sit under 5; 0 sits under 1. The deepest node holding all three in its subtree is the root 3.

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

nodes (comma-separated values)

def lowest_common_ancestor(root, nodes):
    targets = {n.val for n in nodes}
    def dfs(node):
        if not node:
            return None
        left = dfs(node.left)
        right = dfs(node.right)
        if node.val in targets or (left and right):
            return node
        return left or right
    return dfs(root)

function lowestCommonAncestor(root, nodes) {
  const targets = new Set(nodes.map(n => n.val));
  function dfs(node) {
    if (!node) return null;
    const left = dfs(node.left);
    const right = dfs(node.right);
    if (targets.has(node.val) || (left && right)) return node;
    return left || right;
  }
  return dfs(root);
}

class Solution {
    private Set<Integer> targets;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        targets = new HashSet<>();
        for (TreeNode n : nodes) targets.add(n.val);
        return dfs(root);
    }
    private TreeNode dfs(TreeNode node) {
        if (node == null) return null;
        TreeNode left = dfs(node.left);
        TreeNode right = dfs(node.right);
        if (targets.contains(node.val) || (left != null && right != null)) return node;
        return left != null ? left : right;
    }
}

unordered_set<int> targets;
TreeNode* dfs(TreeNode* node) {
    if (!node) return nullptr;
    TreeNode* left = dfs(node->left);
    TreeNode* right = dfs(node->right);
    if (targets.count(node->val) || (left && right)) return node;
    return left ? left : right;
}
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
    for (auto n : nodes) targets.insert(n->val);
    return dfs(root);
}

Explanation

We generalize the classic two-node LCA. First put every target value into a set so membership tests are O(1). Then run one post-order DFS that returns, for each subtree, a single "evidence" node — a node from which all found targets in that subtree are reachable.

At a node, look at what the left and right subtrees returned. If both returned a non-null node, the targets are split across both sides, so this node is their lowest common ancestor and we return it.

If the node itself is a target, it also returns itself: a target counts as containing itself, and it might be the ancestor of others below it.

Otherwise only one side (or neither) had anything, so we bubble up whichever child was non-null. The very first node where both sides report back is the deepest node covering all targets.

Example on [3,5,1,6,2,0,8] with nodes = [6,2,0]: node 5 returns itself (6 and 2 are under it on both sides); node 1 returns itself (0 below). At root 3 both children are non-null → LCA = 3.

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