Lowest Common Ancestor of a Binary Tree IV

Medium Trees & BST LCA Original on LeetCode

Reported atAtlassian

Lowest Common Ancestor of a Binary Tree IV is a medium trees & bst problem solved with the lca pattern. The best approach, optimal (hash set + single postorder pass), runs in O(n + k) time and O(h + k) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from fold pairwise lca up.

Problem

You are given the root of a binary tree whose node values are all distinct, and an array nodes of tree nodes (references into the same tree, all different). Return the lowest common ancestor of every node in nodes.

The lowest common ancestor of a group of nodes is the deepest node of the tree that has each of them as a descendant. A node counts as a descendant of itself, so if one target lies above all the others, that target is the answer.

Examples

Example 1

Input
root = [8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13], nodes = [4, 7, 1]
Output
3
Why
4 and 7 sit under 6, and 1 is the other child of 3, so 3 is the deepest node above all three.

Example 2

Input
same tree, nodes = [13]
Output
13
Why
With a single target, that node is its own lowest common ancestor.

Example 3

Input
same tree, nodes = [6, 4, 13]
Output
8
Why
6 and 4 are in the left subtree of 8, 13 is in the right subtree, so the paths only meet at the root.

Constraints

  • The tree has 1 to 10^4 nodes with distinct values in [-10^9, 10^9].
  • 1 <= nodes.length <= number of nodes
  • Every nodes[i] is a node of the tree, and all of them are different.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Fold pairwise LCAO(n · k)O(h)
Optimal (hash set + single postorder pass)O(n + k)O(h + k)

1Fold pairwise LCA

TimeO(n · k)Each of the k − 1 two-node LCA calls may walk all n nodes.
SpaceO(h)Only the recursion stack, as deep as the tree height h.

The LCA of a group equals LCA(LCA(a, b), c), and so on. Start with the first target and repeatedly replace the current answer with the two-node LCA of it and the next target.

  1. ans = nodes[0].
  2. For every other target x: ans = lca(root, ans, x) with the classic two-node recursion.
  3. Return ans.
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        TreeNode ans = nodes[0];
        for (int i = 1; i < nodes.length; i++) ans = lca(root, ans, nodes[i]);
        return ans;
    }

    private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lca(root.left, p, q);
        TreeNode right = lca(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }
}

2Optimal (hash set + single postorder pass)

TimeO(n + k)Building the set is O(k) and every tree node is visited at most once.
SpaceO(h + k)The hash set holds k nodes and the recursion stack is h deep.

Put all targets in a hash set. Recurse: a null node reports nothing; a target node reports itself (anything below it would only make it the answer anyway). If both children report something, the current node joins targets from two sides, so it is the LCA; otherwise pass up whichever side reported.

  1. targets = set of all nodes in nodes.
  2. dfs(node): if null return null; if node is in targets return node.
  3. left = dfs(node.left), right = dfs(node.right); if both non-null return node, else the non-null one.
  4. Return dfs(root).
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
        Set<TreeNode> targets = new HashSet<>(Arrays.asList(nodes));
        return dfs(root, targets);
    }

    private TreeNode dfs(TreeNode node, Set<TreeNode> targets) {
        if (node == null || targets.contains(node)) return node;
        TreeNode left = dfs(node.left, targets);
        TreeNode right = dfs(node.right, targets);
        if (left != null && right != null) return node;
        return left != null ? left : right;
    }
}

Edge cases to test

  • Only one target node
  • One target is an ancestor of all the others
  • Every node of the tree is a target
  • Targets spread over both subtrees of the root

Hints

Hint 1

You already know how to find the LCA of two nodes. The LCA of many nodes can be built up one node at a time.

Hint 2

Instead of comparing with p and q, ask: is the current node one of the targets? A hash set answers that in O(1).

Hint 3

In one postorder pass, a node whose left and right subtrees both report a target is the answer; a target node reports itself without looking further down.

FAQ

What is the best time complexity for Lowest Common Ancestor of a Binary Tree IV?

Optimal (hash set + single postorder pass) runs in O(n + k) time and O(h + k) extra space. Building the set is O(k) and every tree node is visited at most once.

Which pattern does Lowest Common Ancestor of a Binary Tree IV use?

It is a trees & bst problem that uses the lca pattern. Other problems with the same pattern: Lowest Common Ancestor of a Binary Tree, Lowest Common Ancestor of a Binary Search Tree, Smallest Common Region.

Is there a brute force solution for Lowest Common Ancestor of a Binary Tree IV?

Yes. Fold pairwise LCA takes O(n · k) time and O(h) space. The LCA of a group equals LCA(LCA(a, b), c), and so on.

Which edge cases should I test for Lowest Common Ancestor of a Binary Tree IV?

Only one target node; One target is an ancestor of all the others; Every node of the tree is a target; Targets spread over both subtrees of the root.