Lowest Common Ancestor of a Binary Tree IV
Asked at Atlassian
Problem
Given a binary tree and a list of nodes, find the lowest common ancestor of all the given nodes. The LCA is the deepest node that is an ancestor of every node in the list, where a node can be an ancestor of itself.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | MEDIUM | View all Atlassian questions → |
How to Think About It
Brute force: check every node and verify if all target nodes exist in its subtree.
Use a hash set to store target nodes and return early when a subtree contains them.
Post-order traversal: recurse left and right, merging results upward.
If both left and right return non-null, current node is the LCA.
Optimal: single pass O(n) DFS with a set of targets, returning null if subtree contains zero targets.
Optimal Approach
Perform a depth-first search on the tree. Maintain a set of target nodes. At each node, recurse left and right. If the current node is a target, return it. If both left and right return non-null values, the current node is the LCA. If only one side returns non-null, propagate that result upward. If the current subtree contains fewer targets than the total, return null to signal upward that this subtree is irrelevant. This runs in O(n) time where n is the number of nodes.
What Trips People Up in Real Interviews
Clarify whether a node can be its own ancestor (yes in this variant).
Ask if all nodes are guaranteed to exist in the tree.
Mention that a hash set avoids repeated searches for each target node.
Explain the post-order pattern: process children before the current node.
Discuss how this differs from the classic two-node LCA problem.
Solution Code
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode':
targets = set(nodes)
def dfs(node):
if not node:
return None
if node in targets:
return node
left = dfs(node.left)
right = dfs(node.right)
if left and right:
return node
return left if left else right
return dfs(root)Frequently Asked Questions
What is the Lowest Common Ancestor of a Binary Tree IV problem?
Given a binary tree and a list of nodes, find the lowest common ancestor of all the given nodes. The LCA is the deepest node that is an ancestor of every node in the list, where a node can be an ancestor of itself.
How do you solve Lowest Common Ancestor of a Binary Tree IV?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Lowest Common Ancestor of a Binary Tree IV?
Lowest Common Ancestor of a Binary Tree IV is asked at Atlassian. It is a medium difficulty problem.
What are common mistakes on Lowest Common Ancestor of a Binary Tree IV?
- Clarify whether a node can be its own ancestor (yes in this variant).
- Ask if all nodes are guaranteed to exist in the tree.
- Mention that a hash set avoids repeated searches for each target node.
- Explain the post-order pattern: process children before the current node.
- Discuss how this differs from the classic two-node LCA problem.