45. Valid Escalation Hierarchy

Problem

An org-chart-style escalation hierarchy connects n teams via handoff edges. For escalation routing logic to work correctly, that hierarchy must form a single connected tree: no cycles, and no disconnected components. Validate a candidate edge list.

Teams are numbered 0..n-1. A valid tree requires exactly n-1 edges AND full connectivity with no cycle. This is checked efficiently with Union-Find (disjoint set union): return False immediately if len(edges) != n - 1, since any tree on n nodes has exactly n-1 edges by definition (fewer means disconnected, more means a cycle exists somewhere).

Source: src/45_is_valid_escalation_hierarchy.py

def is_valid_tree(n: int, edges: list[tuple[int, int]]) -> bool:
    ...

>>> is_valid_tree(5, [(0, 1), (0, 2), (0, 3), (1, 4)])
True

>>> is_valid_tree(5, [(0, 1), (1, 2), (2, 3), (1, 3), (1, 4)])
False

>>> is_valid_tree(4, [(0, 1), (1, 2), (0, 2)])
False

Step-by-Step Approach

1. Check the edge count first: if len(edges) != n - 1, return False immediately — this single check rules out both "too few edges to connect everything" (disconnected) and "too many edges" (must contain a cycle), without doing any graph traversal.
2. Initialize a Union-Find (disjoint set) structure: a parent array where parent[i] = i initially, meaning every team starts as its own separate component.
3. Implement find(x) with path compression: follow parent pointers up to the root, and along the way, point each visited node directly at its grandparent (or the root) to flatten the tree for future lookups.
4. For each edge (a, b): find the roots of a and b. If they're already the same root, a and b were already connected by some earlier chain of edges, so this new edge creates a cycle — return False immediately.
5. Otherwise, union the two components by pointing one root at the other (parent[ra] = rb), merging them into a single component.
6. If every edge is processed without detecting a cycle, and the edge count was already confirmed to be exactly n-1, the graph is guaranteed to be a single connected tree — return True.

The key insight is that "exactly n-1 edges" plus "no cycle" together are mathematically equivalent to "fully connected tree" for an n-node graph, so Union-Find only needs to watch for cycles (an edge connecting two nodes already in the same component) — it never has to separately check connectivity, because the edge-count precondition already guarantees that if no cycle ever forms, everything must have merged into one component.

Reference solution

def is_valid_tree(n: int, edges: list[tuple[int, int]]) -> bool:
    # Union-Find with path compression, O(n + e * alpha(n)) time; n-1 edges with
    # no cycle among n nodes is equivalent to full connectivity
    if len(edges) != n - 1:
        return False
    # parent[i] = i, every node starts as its own root
    parent = list(range(n))

    def find(x: int) -> int:
        # walk up until self-pointing root is reached
        while parent[x] != x:
            # path halving: uses halving, not union-by-rank, below
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    # tuple unpacking
    for a, b in edges:
        ra, rb = find(a), find(b)
        if ra == rb:
            return False
        # union step: unconditional, no union-by-rank/size guard
        parent[ra] = rb
    return True

Key Functions & Tricks

• list(range(n)) — initial parent array, each node its own root.
• while parent[x] != x: ... — walks up the parent chain to the root.
• parent[x] = parent[parent[x]] — path halving, roughly halves chain length per find call.
• for a, b in edges — tuple unpacking in the loop header.
• ra, rb = find(a), find(b) — computes both endpoints' roots in one line.
• parent[ra] = rb — union step; unconditional, not rank/size-guided (looser worst-case bound than union-by-rank).

How to Recognize This Pattern