Binary lifting: ancestors and common managers

Last updated: 5 Oct 20269 min read

tutorial

Binary lifting stores the 2^j-th ancestor of each node for successive powers j. A jump of K generations decomposes K into set bits and follows only those table entries. A lowest common ancestor query first raises the deeper node to the other node's depth, then raises both from the largest safe jump downward until their parents match. This reporting-tree implementation rejects duplicate IDs, missing managers, cycles, and disconnected components. It returns None when a requested ancestor lies above the root. The common manager of a node with itself is that node, and a manager is an ancestor of a direct report under the usual inclusive convention.

Operational case

E-19 manages E-26 and E-47; E-26 manages E-52 and E-61; E-47 manages E-83. Two generations above E-52 is E-19. The lowest common manager of E-52 and E-61 is E-26, while the common manager of E-52 and E-83 is E-19. These results depend on the reporting edges staying fixed after preprocessing. Moving E-52 to a new manager invalidates its depth and every jump entry for its descendants. A mutable organization chart needs a rebuild or a different update-aware structure.

Working Python program

"""Static rooted-tree ancestors and lowest common ancestors."""


class ReportingTree:
    def __init__(self, employee_ids: list[str], reports_to: dict[str, str]):
        if not employee_ids or len(employee_ids) != len(set(employee_ids)):
            raise ValueError("employee IDs must be distinct and nonempty")
        self.index = {employee_id: position for position, employee_id in enumerate(employee_ids)}
        if len(reports_to) != len(employee_ids) - 1:
            raise ValueError("one manager relation is required per non-root employee")
        children = [[] for _ in employee_ids]
        child_ids = set()
        for child_id, manager_id in reports_to.items():
            child, manager = self.index[child_id], self.index[manager_id]
            if child == manager or child in child_ids:
                raise ValueError("invalid manager relation")
            child_ids.add(child)
            children[manager].append(child)
        roots = set(range(len(employee_ids))) - child_ids
        if len(roots) != 1:
            raise ValueError("reporting structure needs exactly one root")
        root = roots.pop()
        self.depth = [0] * len(employee_ids)
        parent = [-1] * len(employee_ids)
        visited = {root}
        pending = [root]
        while pending:
            manager = pending.pop()
            for child in children[manager]:
                if child in visited:
                    raise ValueError("reporting structure has a cycle")
                visited.add(child)
                parent[child] = manager
                self.depth[child] = self.depth[manager] + 1
                pending.append(child)
        if len(visited) != len(employee_ids):
            raise ValueError("reporting structure is disconnected")
        self.employee_ids = employee_ids
        self.up = [parent]
        for _ in range(1, len(employee_ids).bit_length()):
            previous = self.up[-1]
            self.up.append([previous[ancestor] if ancestor < 0 else previous[previous[ancestor]] for ancestor in range(len(employee_ids))])

    def ancestor(self, employee_id: str, generations: int) -> str | None:
        if generations < 0:
            raise ValueError("generations must be nonnegative")
        vertex = self.index[employee_id]
        if generations > self.depth[vertex]:
            return None
        bit = 0
        while generations:
            if generations & 1:
                vertex = self.up[bit][vertex]
            generations >>= 1
            bit += 1
        return self.employee_ids[vertex]

    def common_manager(self, first_id: str, second_id: str) -> str:
        left, right = self.index[first_id], self.index[second_id]
        if self.depth[left] < self.depth[right]:
            left, right = right, left
        difference = self.depth[left] - self.depth[right]
        for bit in range(len(self.up)):
            if difference & (1 << bit):
                left = self.up[bit][left]
        if left == right:
            return self.employee_ids[left]
        for bit in range(len(self.up) - 1, -1, -1):
            if self.up[bit][left] != self.up[bit][right]:
                left, right = self.up[bit][left], self.up[bit][right]
        return self.employee_ids[self.up[0][left]]


reporting = ReportingTree(
    ["E-19", "E-26", "E-47", "E-52", "E-61", "E-83"],
    {"E-26": "E-19", "E-47": "E-19", "E-52": "E-26", "E-61": "E-26", "E-83": "E-47"},
)
print(reporting.ancestor("E-52", 2))
print(reporting.common_manager("E-52", "E-61"))
print(reporting.common_manager("E-52", "E-83"))

Output

E-19
E-26
E-19

Time, space, and tradeoff

For N employees, iterative traversal finds parents and depths in O(N) time, then builds O(N log N) ancestor entries in O(N log N) time and space. Ancestor and common-manager queries each take O(log N) time and O(1) additional working space. A single parent walk costs O(height) per request and needs only O(N) parent storage; it may be preferable when queries are rare. The table stores identifiers indirectly through integer positions, so dictionary lookup adds expected O(1) access. The model is one rooted tree, not a general directed reporting graph with multiple managers.

Common Mistakes

Do not index a missing ancestor as if it were a real employee.
Do not compare nodes at different depths before leveling them.
Do not reuse the table after moving a reporting edge.
Do not accept two roots or a cycle as a valid management tree.

Connected lessons

Apply the invariant in the warehouse indexes project, then check the operations quiz.

Cartesian trees: preserve sequence order under a heap minimum adds a distinct structure contract to compare.

Balanced-parentheses trees: encode an ordered hierarchy adds a distinct structure contract to compare.

Euler-tour RMQ: answer static common ancestors in constant query time adds a distinct structure contract to compare.

Kruskal reconstruction trees: answer route bottlenecks through merge ancestors adds a related structure with a different operation boundary.

data structures

range-query-structures