Definition
- LCA of N nodes – the deepest node whose subtree contains every target node in the given set.
- Deduplication – place targets in a
HashSetso duplicates do not inflate the required count. - Post-order count – each node returns how many distinct targets its subtree contains; the count is the sum of children's counts plus one if the node itself is a target.
- Answer – the deepest node whose count equals the number of distinct targets.
- Follow-up – for many queries on a fixed tree, preprocess with Euler tour and sparse table for O(1) pairwise LCA.
Compliance at the National Bank of India flags a group of employees in a suspicious transaction ring. HR needs the lowest-level manager who oversees every one of them. Starting from the bottom up, each manager counts how many of the flagged people fall under them. The deepest manager whose count reaches the full group size is the common boss of the entire ring.
Understanding the Concepts
What is the Lowest Common Ancestor of N nodes?
The LCA of a set of nodes in a tree is the deepest node whose subtree contains every target. For two nodes this is the classic LCA problem. For N nodes, the direct approach is to count coverage rather than trying to extend the two-node algorithm.
package com.bank.model;
public class EmployeeNode {
public String employeeId;
public EmployeeNode left;
public EmployeeNode right;
public EmployeeNode(String employeeId) {
this.employeeId = employeeId;
}
}
How does the counting approach work?
Deduplicate the targets into a HashSet. Run a post-order traversal where each node returns how many distinct targets its subtree contains. A node's count is the sum of its children's counts plus one if the node itself is a target. The deepest node whose count equals the set size is the answer.
package com.bank.service;
import com.bank.model.EmployeeNode;
import java.util.*;
public class LCAOfNNodes {
private EmployeeNode result;
public EmployeeNode findLCA(EmployeeNode root, List<EmployeeNode> targets) {
Set<EmployeeNode> targetSet = new HashSet<>(targets);
result = null;
countTargets(root, targetSet);
return result;
}
private int countTargets(EmployeeNode node, Set<EmployeeNode> targetSet) {
if (node == null) return 0;
int leftCount = countTargets(node.left, targetSet);
int rightCount = countTargets(node.right, targetSet);
int count = leftCount + rightCount + (targetSet.contains(node) ? 1 : 0);
if (count == targetSet.size() && result == null) {
result = node; // deepest node with full count
}
return count;
}
public static void main(String[] args) {
// CEO
// / \
// VP1 VP2
// / \ \
// MGR1 MGR2 MGR3
EmployeeNode ceo = new EmployeeNode("CEO");
EmployeeNode vp1 = new EmployeeNode("VP1");
EmployeeNode vp2 = new EmployeeNode("VP2");
EmployeeNode mgr1 = new EmployeeNode("MGR1");
EmployeeNode mgr2 = new EmployeeNode("MGR2");
EmployeeNode mgr3 = new EmployeeNode("MGR3");
ceo.left = vp1; ceo.right = vp2;
vp1.left = mgr1; vp1.right = mgr2;
vp2.right = mgr3;
LCAOfNNodes finder = new LCAOfNNodes();
// LCA of MGR1 and MGR2 = VP1
EmployeeNode lca = finder.findLCA(ceo, Arrays.asList(mgr1, mgr2));
System.out.println("LCA of MGR1, MGR2: " + lca.employeeId);
// LCA of MGR1 and MGR3 = CEO
lca = finder.findLCA(ceo, Arrays.asList(mgr1, mgr3));
System.out.println("LCA of MGR1, MGR3: " + lca.employeeId);
}
}
LCA of MGR1, MGR2: VP1
LCA of MGR1, MGR3: CEO
Why must you deduplicate the targets?
If the input list contains duplicates (from multiple reports flagging the same employee), the count threshold would be inflated and no node would ever reach it. Deduplication ensures the required count matches the number of distinct targets.
// Without deduplication: duplicate MGR1 inflates count to 3
List<EmployeeNode> targets = Arrays.asList(mgr1, mgr1, mgr2); // size 3
// No subtree contains 3 distinct targets, so LCA is never found!
// With deduplication: {MGR1, MGR2} size 2
Set<EmployeeNode> targetSet = new HashSet<>(targets); // size 2
// VP1's subtree contains both, correctly found
Why is post-order the right traversal order?
Post-order visits children before parents. The first node in post-order whose count reaches the full target size is guaranteed to be the deepest such node. If you used pre-order, the root would match first (since the root's subtree contains everything) and you would get the shallowest, not the deepest.
// Post-order guarantees deepest-first discovery
private int countTargets(EmployeeNode node, Set<EmployeeNode> targets) {
if (node == null) return 0;
int left = countTargets(node.left, targets); // children first
int right = countTargets(node.right, targets); // children first
int count = left + right + (targets.contains(node) ? 1 : 0);
if (count == targets.size() && result == null) {
result = node; // first full-count node in post-order = deepest
}
return count;
}
What is the Euler-tour and sparse-table follow-up?
If the tree is fixed and you receive thousands of queries, a linear traversal per query is wasteful. Preprocess with an Euler tour (recording nodes in DFS visit order with depths) and build a sparse table for range-minimum queries. Then any pairwise LCA is answered in O(1) time.
// Euler tour preprocessing (conceptual)
int[] eulerTour; // node indices in DFS visit order
int[] depth; // depth of each entry in the tour
int[] firstOccurrence; // first index in tour for each node
// Sparse table for range-minimum query on depth[]
// LCA(u, v) = eulerTour[RMQ(firstOccurrence[u], firstOccurrence[v])]
// For N targets, fold pairwise:
// LCA(a, b, c) = LCA(LCA(a, b), c)
// K targets → K-1 constant-time pair queries
How do you fold pairwise for multi-target queries?
The LCA of a set is computed by folding: LCA(a, b, c) = LCA(LCA(a, b), c). With O(1) pairwise LCA from the sparse table, K targets need K-1 pair queries.
public EmployeeNode lcaOfSet(List<EmployeeNode> targets) {
EmployeeNode result = targets.get(0);
for (int i = 1; i < targets.size(); i++) {
result = lcaPair(result, targets.get(i)); // O(1) with sparse table
}
return result;
}
What is the time and space complexity?
| Approach | Preprocessing | Per Query | Space |
|---|---|---|---|
| Post-order counting | None | O(N + K) | O(N) |
| Euler tour + sparse table | O(N log N) | O(K) | O(N log N) |
For a single query, the counting approach is simpler. For thousands of queries on the same tree, the Euler-tour preprocessing pays for itself many times over.
What should a senior engineer know?
Recognizing the preprocessing-versus-per-query tradeoff is the heart of the follow-up. This same reasoning drives caching and indexing decisions in real systems: invest upfront to make repeated lookups cheap.
In production at National Bank of India, the fraud investigation team flags groups of employees. The org-tree service uses the counting traversal for one-off investigations and switches to the Euler-tour sparse table when a large case fires thousands of group queries against the same fixed org hierarchy.
// Decision logic for query strategy
if (queryCount > THRESHOLD) {
preprocessEulerTour(root); // O(N log N) one-time cost
for (Query q : queries) {
result = lcaOfSet(q.targets); // O(K) per query
}
} else {
for (Query q : queries) {
result = findLCA(root, q.targets); // O(N + K) per query
}
}
Visual Overview
Post-Order Counting
CEO (count=3, all targets found → but not deepest)
/ \
VP1 VP2
(2/2) (1/2)
/ \ \
MGR1 MGR2 MGR3
(1) (1) (1)
Targets: {MGR1, MGR2}
Post-order visits: MGR1(1), MGR2(1), VP1(2=full!) → VP1 is LCA
CEO also has count=2, but VP1 was found first in post-order
Euler Tour (DFS order with depths)
Visit: CEO VP1 MGR1 VP1 MGR2 VP1 CEO VP2 MGR3 VP2 CEO
Depth: 0 1 2 1 2 1 0 1 2 1 0
LCA(MGR1, MGR2) = shallowest node between their first occurrences
= VP1 (depth 1)
Key Takeaway
The Lowest Common Ancestor of a set of nodes generalizes the classic two-node LCA. The clean approach is counting coverage: deduplicate the targets into a set, run a post-order traversal where each node reports how many distinct targets its subtree contains, and the deepest node with a full count is the answer. Post-order guarantees deepest-first discovery because children are visited before parents.
Deduplication is essential because duplicate targets from multiple reports would inflate the required count, making the LCA unfindable. The counting approach is simpler and more general than trying to extend the two-node algorithm with pairwise pairing.
The follow-up changes the economics entirely. If the tree is fixed but you receive thousands of queries, repeating a linear traversal each time is wasteful. Preprocessing with an Euler tour and sparse table gives O(1) pairwise LCA, and folding pairwise over K targets takes only K-1 constant-time pair queries. Recognizing this preprocessing-versus-per-query tradeoff is the senior-level insight the interviewer is testing.
In our banking system at National Bank of India, the fraud investigation team flags groups of employees and needs the lowest-level manager overseeing all of them. The org-tree service uses the counting traversal for one-off investigations and switches to the Euler-tour sparse table when a large case fires thousands of group queries against the same hierarchy.
Remember one sentence: deduplicate targets, count per subtree in post-order, and the deepest node with a full count is the LCA of the group.
---