Find the Lowest Common Manager of Two Employees

Problem Statement

A company's org chart is a tree — each employee has one manager, and the CEO is the root. Given the org tree and two employees, find their lowest common manager (the deepest person who is a manager, directly or indirectly, of both).

Every employee node has a value and a list of direct reports.

Constraints

• 1 <= number of employees <= 10^5
• Both employees are guaranteed to exist in the tree
• An employee can be considered a manager of themselves for this problem

Example

              CEO
             /   \
           VP-A   VP-B
          /   \      \
        Amy   Bob    Cara
       /  \
     Dan  Eve

lowestCommonManager(Dan, Eve) = Amy
lowestCommonManager(Dan, Bob) = VP-A
lowestCommonManager(Amy, Cara) = CEO

The Insight — LCA via Single DFS

This is Lowest Common Ancestor (LCA) reframed as an org chart. The elegant O(n) solution uses a single post-order DFS that returns two pieces of info per node at once.

The trick — each recursive call returns a pair: (numTargetsFound, lcaNode).

For a node, recurse into all its reports and sum up how many of the two targets were found in its subtrees. Then:

• If a node's subtree (including itself) contains both targets AND no deeper node already claimed the LCA, this node is the answer.
• The first node (deepest, because it's post-order) where the count reaches 2 is the lowest common manager.

def helper(node, t1, t2):
    numFound = (1 if node in (t1, t2) else 0)
    for report in node.reports:
        found, lca = helper(report, t1, t2)
        if lca: return (found, lca)          # already found below
        numFound += found
    if numFound == 2: return (2, node)       # this node is the LCA
    return (numFound, None)

The beauty: you find the answer in one traversal without storing parent pointers or paths to root. The "return count + candidate" pattern is what makes it clean — and it generalizes to LCA of K nodes.

Follow-ups

1. What if you had parent pointers instead of a top-down tree? (walk up + set intersection)
2. How would you find the LCA of K employees, not just 2?
3. What if the same employee could report to two managers (a DAG, not a tree)?
4. How would you answer millions of LCA queries efficiently? (binary lifting / Euler tour + sparse table)