Number Of Ways To Reconstruct A Tree

Number Of Ways To Reconstruct A Tree

What is this problem about?

The Number Of Ways To Reconstruct A Tree problem gives you pairs of nodes that must be ancestor-descendant in a rooted tree. Find whether 0, 1, or infinitely many trees satisfy all constraints. This hard tree problem requires identifying which configurations of constraints lead to unique trees, multiple trees, or no valid tree.

Why is this asked in interviews?

Uber asks this hard problem to test deep tree reasoning — specifically, understanding when ancestor-descendant constraints over-determine or under-determine a tree structure. The array, hash table, graph, simulation, and tree interview pattern is comprehensively tested.

Algorithmic pattern used

Degree analysis + constraint verification. Build an adjacency-like structure from pairs. Sort nodes by degree (number of pairs they appear in). For the root candidate (highest degree), verify all constraints. The key insights: (1) if a node has degree = n-1, it must be the root; (2) for each pair, one node must be ancestor of the other; (3) if two nodes have the same "ancestor set," either arrangement is valid → infinite ways; (4) conflicting requirements → 0 ways; (5) unique valid tree → 1 way.

Example explanation

Pairs: [(1,2),(1,3),(2,3)]. Node degrees: 1→2, 2→2, 3→1. Analysis: node 1 and 2 both have 2 pairs. Either could be parent of the other in some configurations. Determine if the constraint graph has a valid topological tree structure. If so, check for ambiguities.

Common mistakes candidates make

• Trying to enumerate all possible trees (exponential).
• Not recognizing the degree-based analysis shortcut.
• Missing the "infinite ways" case (two nodes with identical ancestor sets).
• Not verifying transitivity of ancestor-descendant pairs.

Interview preparation tip

"How many valid structures satisfy these constraints?" problems for trees often reduce to: (1) find the unique valid root (highest degree node must be root if degree = n-1), (2) verify each constraint, (3) detect ambiguities (equal-degree node pairs) that allow infinite arrangements. Practice constraint-satisfaction problems on trees by working from first principles — derive the conditions for 0/1/infinity manually on small examples before generalizing.