#1719

Hard

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Number Of Ways To Reconstruct A Tree

Determine how many distinct rooted trees can be reconstructed from given node pairs using careful traversal and state tracking.

tree graph

Problem Statement

You are given an array of unique pairs where each pair represents two nodes that are connected in an unknown rooted tree. Your task is to count all possible rooted trees that satisfy these connections while maintaining a valid parent-child hierarchy.

Two reconstructions are considered different if at least one node has a different parent between them. Ensure that your solution leverages binary-tree traversal and state tracking to handle all nodes and detect scenarios where multiple reconstructions or impossibilities arise.

Examples

Example 1

Input: pairs = [[1,2],[2,3]]

Output: 1

There is exactly one valid rooted tree, which is shown in the above figure.

Example 2

Input: pairs = [[1,2],[2,3],[1,3]]

Output: 2

There are multiple valid rooted trees. Three of them are shown in the above figures.

Example 3

Input: pairs = [[1,2],[2,3],[2,4],[1,5]]

Output: 0

There are no valid rooted trees.

Constraints

1 <= pairs.length <= 105
1 <= xi < yi <= 500
The elements in pairs are unique.

Solution Approach

Identify the Root Node

Find the node that appears in pairs with every other node. This node must be the root because the root connects directly or indirectly to all other nodes in the reconstruction. If no such node exists, immediately return 0.

Construct Adjacency and Track States

Build an adjacency map from the pairs and initialize state tracking for each node, recording potential parents and children. Traverse the tree inductively, updating the parent of each node only if it satisfies the adjacency constraints and maintaining the hierarchy integrity.

Check for Multiple Reconstructions

During traversal, if multiple nodes have equal parent eligibility, mark the solution as having multiple valid reconstructions. Validate all nodes to ensure each parent assignment is consistent; if conflicts arise, the tree is impossible and the answer is 0.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time and space complexity depend on building adjacency maps and traversing all nodes, typically O(N + E), where N is the number of nodes and E is the number of pairs, but state tracking adds additional overhead in worst cases.

What Interviewers Usually Probe

Looks for correct identification of the root node across all pairs.
Watches for proper handling of multiple valid reconstructions using state tracking.
Checks whether the traversal maintains consistent parent-child relationships across the tree.

Common Pitfalls or Variants

Common pitfalls

Assuming any node with highest degree is root without verifying it connects to all others.
Failing to track multiple valid parent candidates, missing multiple reconstructions.
Overlooking conflicts in adjacency that make a tree impossible, returning incorrect counts.

Follow-up variants

Counting reconstructions for a tree with weighted edges.
Handling disconnected node pairs that cannot form a single rooted tree.
Extending to allow n-ary trees instead of strictly binary traversal.

FAQ

What is the first step in solving Number Of Ways To Reconstruct A Tree?

Identify the root node that appears in pairs with all other nodes, as this node must be the root for any valid reconstruction.

How does binary-tree traversal help in this problem?

It allows you to inductively assign parents and children while checking adjacency constraints and tracking node states efficiently.

Can multiple valid trees exist for the same pairs?

Yes, when nodes have equal eligibility to be parents of their children, multiple reconstructions are possible, requiring careful state tracking.

What should I do if no node connects to all others?

The tree is impossible in this case, so you should return 0 as there is no valid reconstruction.

How do I avoid common mistakes in parent assignment?

Maintain an adjacency map and state tracker for each node, and verify each parent assignment against all connected nodes before proceeding.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

class Solution:
    def checkWays(self, pairs: List[List[int]]) -> int:
        g = [[False] * 510 for _ in range(510)]
        v = defaultdict(list)
        for x, y in pairs:
            g[x][y] = g[y][x] = True
            v[x].append(y)
            v[y].append(x)
        nodes = []
        for i in range(510):
            if v[i]:
                nodes.append(i)
                g[i][i] = True
        nodes.sort(key=lambda x: len(v[x]))
        equal = False
        root = 0
        for i, x in enumerate(nodes):
            j = i + 1
            while j < len(nodes) and not g[x][nodes[j]]:
                j += 1
            if j < len(nodes):
                y = nodes[j]
                if len(v[x]) == len(v[y]):
                    equal = True
                for z in v[x]:
                    if not g[y][z]:
                        return 0
            else:
                root += 1
        if root > 1:
            return 0
        return 2 if equal else 1

Continue Practicing

#1916 count ways to build rooms in an ant colony #1377 frog position after t seconds #1361 validate binary tree nodes