Lowest common manager in an org chart

The org chart is a rooted n-ary tree, so the lowest common manager is the
lowest common ancestor (LCA) of the two employees. "Lowest" means deepest:
of all the people who have both employees in their reporting chain, pick the
one farthest from the top. An employee counts as being in their own chain, so
if one employee manages the other (directly or indirectly), the manager is
the answer.

Brute force: compare chains of command. Walk the tree once to record each
employee's manager, build the chain from each target up to the root, put one
chain in a set, and walk the other upward until it hits a member of the set.
That is O(n) time and O(n) extra space for the parent map. It is a fine first
answer and it is the right shape when queries repeat (see follow-ups).

Optimal single pass: count targets per subtree. Do one post-order DFS. Each
call returns how many of the targets live in its subtree (itself included).
The first node, in post-order, whose count reaches the number of targets is
the answer. Post-order guarantees that children finish before their parent,
so the first node to see both targets is the deepest one. Once the answer is
set, every ancestor also sees the full count, but we only keep the first.

Invariants:

• count(node) = number of distinct targets in node's subtree.
• The answer is set exactly once, at the deepest node with count == k.
• If the full count is never reached, a target is not in the tree, and we
  return None instead of a wrong manager. This is the trap in the binary
  LCA "return the node if it matches" shortcut: it assumes both targets exist.

Counting (instead of the classic "return the node you found") generalizes for
free to any number of employees, which is the usual part 2.

Real org charts can be thousands of levels deep in a bad case (a long chain),
so the code uses an explicit stack rather than Python recursion.

from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable, Optional


@dataclass(eq=False)
class Employee:
    name: str
    reports: list[Employee] = field(default_factory=list)


def lowest_common_manager(
    root: Optional[Employee], targets: Iterable[Employee]
) -> Optional[Employee]:
    """Deepest employee whose subtree contains every target (a node is in its own subtree).

    Returns None if the tree is empty, no targets are given, or any target is missing.
    """
    wanted = {id(t) for t in targets}
    if root is None or not wanted:
        return None

    counts: dict[int, int] = {}
    answer: Optional[Employee] = None
    # Iterative post-order: (node, children_done)
    stack: list[tuple[Employee, bool]] = [(root, False)]
    while stack:
        node, done = stack.pop()
        if not done:
            stack.append((node, True))
            for child in node.reports:
                stack.append((child, False))
            continue
        total = 1 if id(node) in wanted else 0
        for child in node.reports:
            total += counts.pop(id(child))
        counts[id(node)] = total
        if answer is None and total == len(wanted):
            answer = node
    return answer


def lcm_pair(root: Optional[Employee], a: Employee, b: Employee) -> Optional[Employee]:
    """The classic two-employee form of the question."""
    return lowest_common_manager(root, [a, b])


def lcm_by_chain(root: Employee, a: Employee, b: Employee) -> Optional[Employee]:
    """Brute force: build a parent map, then intersect the two chains of command."""
    parent: dict[int, Optional[Employee]] = {id(root): None}
    stack = [root]
    while stack:
        node = stack.pop()
        for child in node.reports:
            parent[id(child)] = node
            stack.append(child)
    if id(a) not in parent or id(b) not in parent:
        return None

    seen: set[int] = set()
    cur: Optional[Employee] = a
    while cur is not None:
        seen.add(id(cur))
        cur = parent[id(cur)]
    cur = b
    while cur is not None:
        if id(cur) in seen:
            return cur
        cur = parent[id(cur)]
    return None  # unreachable: both chains end at root


if __name__ == "__main__":
    #            ceo
    #        /    |     \
    #     vp_a   vp_b   vp_c
    #    /   \     |
    #  m1    m2    m3
    #  / \          |
    # e1  e2        e3
    e1, e2, e3 = Employee("e1"), Employee("e2"), Employee("e3")
    m1 = Employee("m1", [e1, e2])
    m2 = Employee("m2")
    m3 = Employee("m3", [e3])
    vp_a = Employee("vp_a", [m1, m2])
    vp_b = Employee("vp_b", [m3])
    vp_c = Employee("vp_c")
    ceo = Employee("ceo", [vp_a, vp_b, vp_c])

    for f in (lcm_pair, lcm_by_chain):
        assert f(ceo, e1, e2) is m1
        assert f(ceo, e1, m2) is vp_a
        assert f(ceo, e2, e3) is ceo
        assert f(ceo, m1, e2) is m1          # manager of the other
        assert f(ceo, e3, e3) is e3          # same employee
        assert f(ceo, ceo, vp_c) is ceo
        assert f(ceo, e1, Employee("x")) is None  # not in the org

    assert lowest_common_manager(ceo, [e1, e2, m2]) is vp_a
    assert lowest_common_manager(ceo, [e1, e3, vp_c]) is ceo
    assert lowest_common_manager(ceo, []) is None
    assert lowest_common_manager(None, [e1]) is None

    # Deep chain: no recursion limit
    deep_root = cur = Employee("d0")
    nodes = [cur]
    for i in range(1, 50_000):
        nxt = Employee(f"d{i}")
        cur.reports.append(nxt)
        cur = nxt
        nodes.append(cur)
    assert lcm_pair(deep_root, nodes[30_000], nodes[-1]) is nodes[30_000]
    print("ok")

• lowest_common_manager: O(n) time, one visit per employee. O(h) for the
  stack in a chain-shaped tree up to O(n) for the stack plus pending counts in
  a wide tree; overall O(n) worst case. It accepts k targets at no extra cost
  beyond the O(k) set.
• lcm_by_chain: O(n) time and O(n) space for the parent map; the chain walk
  itself is O(h).
• With a prebuilt parent map and depths, each pair query is O(h) and needs no
  traversal; with binary lifting it is O(log n) per query after O(n log n)
  preprocessing.

Using the tree in the code (ceo -> vp_a, vp_b, vp_c; vp_a -> m1, m2;
m1 -> e1, e2; vp_b -> m3 -> e3):

• (e1, e2) -> m1 (siblings under the same manager)
• (e1, m2) -> vp_a (different depths)
• (e2, e3) -> ceo (different branches, meet only at the root)
• (m1, e2) -> m1 (one employee manages the other)
• (e3, e3) -> e3 (same employee twice)
• (ceo, vp_c) -> ceo (root is one of the targets)
• (e1, outsider) -> None (target not in the org)
• [e1, e2, m2] -> vp_a (three employees)
• Empty target list or empty tree -> None
• A 50,000-level chain -> correct answer with no recursion error

1. Any number of employees. The counting DFS already handles k targets:
   the answer is the first node whose subtree count reaches k. The chain
   approach generalizes by intersecting k chains, or by folding pairwise LCA
   over the list (LCA is associative), which is O(k * h) with a parent map.
2. Many queries on the same org. Precompute parent and depth in one pass.
   Then each query lifts the deeper employee to the same depth and walks both
   up together: O(h). For very deep trees use binary lifting (O(log n) per
   query, O(n log n) memory), or an Euler tour plus a sparse-table range
   minimum for O(1) queries.
3. Input is a list of records, not a tree. Given rows like
   (id, name, manager_id), build children and parent maps, find the root
   (the one row with no manager), and reject the input if there are zero or
   several roots, a cycle, or a manager id that does not exist. Then reuse the
   parent-map method directly; no tree object is needed.
4. Lookup by name. Keep a name -> Employee dict built during the first
   traversal. Handle duplicate names explicitly (error, or use ids), because
   the question promises uniqueness but real data does not.
5. The org changes (hires, departures, re-orgs). With parent pointers a
   move is O(1) and pair queries stay O(h). If queries are heavy and edits are
   rare, rebuild the binary-lifting table lazily; for heavy edits on huge
   trees, link-cut trees give O(log n) amortized for both, which is worth
   naming but not coding.

Mid-level (L4)

• Recognizes the problem as LCA on an n-ary tree and states the definition
  (deepest node, a node counts as its own descendant).
• Writes a working recursive solution for two employees with O(n) time.
• Tests siblings, different branches, and the "one manages the other" case.

Senior (L5)

• Asks whether both employees are guaranteed to exist and returns None
  correctly when they are not, instead of relying on the binary-LCA shortcut.
• Uses the counting formulation so k employees falls out naturally.
• Mentions recursion depth on deep or chain-shaped orgs and offers an
  iterative traversal; compares the parent-map method and when it wins.

Staff (L6+)

• Separates one-off queries from a query service: preprocess once
  (parent/depth, binary lifting, or Euler tour + RMQ) and states the trade-offs.
• Handles messy input: building the tree from records, validating a single
  root, cycles, dangling manager ids, duplicate names.
• Discusses keeping answers correct while the org changes, and what to cache
  and invalidate.