Read-Heavy Org Chart Subordinate Counts

0) Problem Restatement

Microsoft asked: given manager → direct report relationships for an organization (each employee has at most one manager, and the CEO has none), build a data structure or service that:

1. Query (read-heavy): given an employee, return their total number of subordinates, direct and indirect.
2. Updates (occasional): add an employee under a manager, remove an employee, or move someone (and their whole team) to a new manager.

1) Precompute Subtree Sizes

Store the tree as children[manager] = [reports]. The subordinate count of X = the size of X's subtree − 1. Compute all counts with one post-order DFS: count(X) = Σ (count(child) + 1). That's O(n) once, and then each query is O(1).

from collections import defaultdict

class OrgChart:
    def __init__(self, pairs):                   # pairs: (manager, report)
        self.parent, self.children = {}, defaultdict(list)
        for m, r in pairs:
            self.parent[r] = m; self.children[m].append(r)
        people = set(self.parent) | set(self.children)
        self.count = {p: 0 for p in people}
        roots = [p for p in people if p not in self.parent]
        for root in roots:                        # iterative post-order DFS (no recursion limit)
            stack, order = [root], []
            while stack:
                n = stack.pop(); order.append(n); stack.extend(self.children[n])
            for n in reversed(order):
                self.count[n] = sum(self.count[c] + 1 for c in self.children[n])

    def subordinates(self, e):
        return self.count[e]

    def _bump_ancestors(self, start, delta):
        a = start
        while a is not None:
            self.count[a] += delta; a = self.parent.get(a)

    def add(self, manager, e):
        self.parent[e] = manager; self.children[manager].append(e); self.count[e] = 0
        self._bump_ancestors(manager, 1)

    def move(self, e, new_manager):              # e keeps its whole team
        size = self.count[e] + 1
        old = self.parent[e]
        self.children[old].remove(e); self._bump_ancestors(old, -size)
        self.parent[e] = new_manager; self.children[new_manager].append(e)
        self._bump_ancestors(new_manager, size)

2) Update Costs

• Add under M: +1 to M and all of M's ancestors → O(depth). Org charts are shallow (depth ~10–15), so this is cheap.
• Remove a leaf: −1 up the chain. Removing a manager: decide whether their reports move to the manager's manager (then only the removed person leaves: −1 up the chain) or the whole team leaves (−(size) up the chain).
• Move a subtree of size s: −s along the old ancestors, +s along the new ones. Check the new manager isn't inside the moved subtree (that would create a cycle).

3) Alternative for Very Deep Trees or Frequent Moves

4) As a Service

flowchart LR
    HR["HR system - changes"] --> SVC["Org service - in-memory tree + counts"]
    SVC --> DB[("Employees table - manager_id")]
    API["Query API"] --> SVC
    SVC --> CACHE[("Cache / replicas for reads")]

• Keep the tree and counts in memory (even 1M employees is small), rebuilt from the DB at startup, and updated incrementally on HR change events.
• Read replicas of the service handle heavy read traffic. Updates go through one writer (or with version checks) to avoid races.

5) Wrap-Up

Build the tree from manager–report pairs and precompute every employee's subordinate count with one post-order DFS, so queries are O(1). Apply updates by walking the ancestor chain (O(depth), small in real org charts), adding or subtracting the moved subtree's size and rejecting cyclic moves. For deep trees or heavy churn, use an Euler tour with a Fenwick tree, and serve it all from an in-memory service with replicas for the read-heavy load.