Lowest Common Ancestor of a Binary Tree IV
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
1to10^4nodes 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| Fold pairwise LCA | O(n · k) | O(h) |
| Optimal (hash set + single postorder pass) | O(n + k) | O(h + k) |
1Fold pairwise LCA
O(n · k)Each of the k − 1 two-node LCA calls may walk all n nodes.O(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.
ans = nodes[0].- For every other target
x:ans = lca(root, ans, x)with the classic two-node recursion. - 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;
}
}class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
ans = nodes[0]
for i in range(1, len(nodes)):
ans = self.lca(root, ans, nodes[i])
return ans
def lca(self, root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
if root is None or root is p or root is q:
return root
left = self.lca(root.left, p, q)
right = self.lca(root.right, p, q)
if left is not None and right is not None:
return root
return left if left is not None else rightclass Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
TreeNode* ans = nodes[0];
for (size_t i = 1; i < nodes.size(); i++) ans = lca(root, ans, nodes[i]);
return ans;
}
private:
TreeNode* lca(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr || root == p || root == q) return root;
TreeNode* left = lca(root->left, p, q);
TreeNode* right = lca(root->right, p, q);
if (left != nullptr && right != nullptr) return root;
return left != nullptr ? left : right;
}
};function lowestCommonAncestor(root, nodes) {
let ans = nodes[0];
for (let i = 1; i < nodes.length; i++) ans = lca(root, ans, nodes[i]);
return ans;
}
function lca(root, p, q) {
if (root === null || root === p || root === q) return root;
const left = lca(root.left, p, q);
const right = lca(root.right, p, q);
if (left !== null && right !== null) return root;
return left !== null ? left : right;
}2Optimal (hash set + single postorder pass)
O(n + k)Building the set is O(k) and every tree node is visited at most once.O(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.
targets= set of all nodes innodes.- dfs(node): if null return null; if node is in
targetsreturn node. - left = dfs(node.left), right = dfs(node.right); if both non-null return node, else the non-null one.
- 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;
}
}class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
targets = set(nodes)
return self.dfs(root, targets)
def dfs(self, node: Optional[TreeNode], targets: Set[TreeNode]) -> Optional[TreeNode]:
if node is None or node in targets:
return node
left = self.dfs(node.left, targets)
right = self.dfs(node.right, targets)
if left is not None and right is not None:
return node
return left if left is not None else rightclass Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, vector<TreeNode*>& nodes) {
unordered_set<TreeNode*> targets(nodes.begin(), nodes.end());
return dfs(root, targets);
}
private:
TreeNode* dfs(TreeNode* node, unordered_set<TreeNode*>& targets) {
if (node == nullptr || targets.count(node)) return node;
TreeNode* left = dfs(node->left, targets);
TreeNode* right = dfs(node->right, targets);
if (left != nullptr && right != nullptr) return node;
return left != nullptr ? left : right;
}
};function lowestCommonAncestor(root, nodes) {
const targets = new Set(nodes);
return dfs(root, targets);
}
function dfs(node, targets) {
if (node === null || targets.has(node)) return node;
const left = dfs(node.left, targets);
const 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.