Number of Ways to Reconstruct a Tree: Ancestor Pair Analysis

You are given an array of pairs where pairs[i] = [xi, yi] means that xi is an ancestor of yi or yi is an ancestor of xi in some rooted tree. Your job is to determine whether exactly one valid tree exists that produces those pairs, multiple valid trees exist, or no valid tree exists at all. Return 0, 1, or 2 accordingly.

This is LeetCode 1719: Number of Ways to Reconstruct a Tree, one of the harder tree problems on the platform. It asks you to work backwards from ancestor relationships to figure out if a consistent tree structure is possible.

Why this problem matters

This problem forces you to think deeply about what ancestor relationships actually encode about tree structure. In most tree problems, you are given the tree and asked to compute something. Here, you are given a flattened summary of the tree's ancestor relationships and asked to reverse-engineer whether the tree is unique, ambiguous, or impossible. That reversal is a powerful mental model that shows up in constraint satisfaction problems, dependency resolution, and data reconstruction tasks.

Understanding how degree (the number of ancestor pairs a node participates in) relates to depth in a tree is a building block you will reuse. The root of a tree is an ancestor of every other node, so it must appear in the most pairs. Leaf nodes appear in the fewest. Sorting by degree gives you a natural ordering that mirrors the tree's hierarchy, and that insight unlocks the entire algorithm.

The key insight

The root of the tree must be an ancestor of every other node, which means it appears in exactly n - 1 pairs (one pair with each other node). If no node has degree n - 1, no valid tree exists.

Once you identify the root, you process the remaining nodes in order of decreasing degree. For each node, its parent must be the node with the smallest adjacency set that is still a superset of the current node's adjacency set. This is because a parent is an ancestor of everything its child is an ancestor of, plus possibly more.

The critical check is the subset relationship: every node that the child connects to in the pairs must also be connected to the parent. If the child's adjacency set is not a subset of the parent's, the pairs are inconsistent and no valid tree exists.

Finally, if a child and its parent have the same adjacency set size, the two nodes are interchangeable. You could swap which one is the parent and which is the child, and both arrangements would produce the same set of ancestor pairs. That means multiple valid trees exist.

The algorithm:

1. Build adjacency sets from the pairs.
2. Sort nodes by the size of their adjacency set (degree).
3. For each node, find its parent (smallest superset among candidates).
4. Verify the parent-child relationship is consistent.
5. If any node has the same degree as its parent, multiple trees are possible.

The solution

def check_ways(pairs: list[list[int]]) -> int:
    from collections import defaultdict

    adj = defaultdict(set)
    for x, y in pairs:
        adj[x].add(y)
        adj[y].add(x)

    nodes = sorted(adj.keys(), key=lambda x: len(adj[x]), reverse=True)
    root = nodes[0]

    if len(adj[root]) != len(nodes) - 1:
        return 0

    result = 1
    for node in nodes:
        adj[node].add(node)

    for i in range(1, len(nodes)):
        node = nodes[i]
        parent = None
        parent_size = float('inf')

        for candidate in adj[node]:
            if candidate == node:
                continue
            if len(adj[candidate]) >= len(adj[node]) and len(adj[candidate]) < parent_size:
                parent = candidate
                parent_size = len(adj[candidate])

        if parent is None:
            return 0

        if not adj[node].issubset(adj[parent]):
            return 0

        if len(adj[node]) == len(adj[parent]):
            result = 2

    return result

The code starts by building adjacency sets from the input pairs. For each pair [x, y], both x and y are added to each other's sets. Then it sorts all nodes by their degree in descending order. The node with the highest degree is the candidate root, and it must have degree n - 1 (connected to every other node). If that check fails, we return 0 immediately.

Next, each node adds itself to its own adjacency set. This is a subtle but important step. It ensures that the subset check later works correctly, because a node is trivially an ancestor of itself. The self-inclusion means that when we check adj[node].issubset(adj[parent]), we are asking: "Is every node related to this child also related to the parent?" That is exactly the condition a valid tree must satisfy.

For each non-root node, we search for its parent among the nodes in its adjacency set. The parent should have the smallest adjacency set that is still at least as large as the child's. If no such parent exists, the tree is impossible. If the subset check fails, the pairs are contradictory. And if the child and parent have identical set sizes, they are interchangeable, so we flag result = 2. At the end, if everything checks out and no equal-degree pair was found, exactly one valid tree exists.

Visual walkthrough

Let's trace through the algorithm step by step with pairs = [[1,2],[2,3],[1,3]]. All three nodes are connected to each other, which means every pair of nodes has an ancestor relationship. That is consistent with a linear chain (like 1 -> 2 -> 3) but also with other arrangements.

The walkthrough confirms that the algorithm catches the ambiguity. Nodes 1 and 2 have identical adjacency sets after adding themselves, so swapping their roles (root vs. child) produces equally valid trees. The algorithm detects this through the equal-degree check and returns 2.

Complexity analysis

Time: Sorting the nodes takes O(n log n). For each of the n nodes, the parent search iterates over the node's adjacency set (up to n elements), and the subset check takes O(n) in the worst case. This gives O(n^2) overall. The subset check dominates, since in a tree where every pair is an ancestor pair (a linear chain), each adjacency set has O(n) entries.

Space: The adjacency sets store each pair twice (once in each direction), and with up to O(n^2) pairs in a complete ancestor structure, the total space is O(n^2). The sorted node list and other auxiliary variables use O(n).

The building blocks

1. Degree-based ordering in trees

Sorting nodes by the number of relationships they participate in reveals the tree's hierarchy from root to leaves:

nodes = sorted(adj.keys(), key=lambda x: len(adj[x]), reverse=True)
root = nodes[0]

In any rooted tree, the root is an ancestor of every other node, so it appears in the most pairs. Each subsequent layer of the tree appears in fewer pairs. This degree-based ordering is a common technique in problems where you need to reconstruct or validate a hierarchical structure. You will see similar ideas in problems involving dominator trees and topological orderings.

2. Subset validation for ancestor relationships

Checking that a child's adjacency set is contained within its parent's adjacency set:

if not adj[node].issubset(adj[parent]):
    return 0

This one-line check encodes a deep property of trees. If node A is the parent of node B, then every ancestor of B (except B itself) is also an ancestor of A. Equivalently, every node that has a pair with B must also have a pair with A. Python's set.issubset method runs in O(min(len(s), len(t))) time, making this check efficient. The same subset pattern shows up in problems involving hierarchical clustering and nested interval validation.

Edge cases

• Single node: Only one node, zero pairs. There is exactly one valid tree (the node itself). Return 1.
• Two nodes: One pair [x, y]. Exactly one valid tree exists with one as root and the other as child. Return 1.
• Linear chain (each node has one child): Pairs form a complete ancestor structure. If all degrees are distinct, there is exactly one valid chain. If any two adjacent nodes have the same degree, multiple orderings exist.
• Star graph (root connected to all): The root has degree n - 1 and every leaf has degree 1. All leaves connect only to the root. This produces exactly one valid tree. Return 1.
• Impossible pairs: If the node with the highest degree does not have degree n - 1, no single root can account for all the pairs. Return 0. Also, if a child's adjacency set is not a subset of its parent's, the pairs are contradictory. Return 0.

From understanding to recall

This problem has a lot of moving parts: adjacency set construction, degree sorting, root validation, parent finding, subset checking, and the equal-degree rule. Reading through the solution once gives you the idea, but reproducing it from scratch under interview pressure is a different challenge entirely.

Spaced repetition helps you internalize each piece separately. Practice building adjacency sets from pairs. Practice the subset check and understand why self-inclusion matters. Practice the equal-degree detection logic. When each building block is automatic, assembling the full solution becomes a matter of connecting familiar pieces rather than reinventing the algorithm from scratch.

Related posts

• Validate Binary Search Tree - Another tree validation problem where structural constraints must be verified
• Course Schedule - Graph-based dependency analysis with similar topological reasoning
• Serialize and Deserialize Binary Tree - Reconstructing trees from encoded representations

CodeBricks breaks Number of Ways to Reconstruct a Tree into its degree-sorting and subset-validation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a hard tree reconstruction problem shows up in your interview, you already know the moves.