Practice Number Of Ways To Reconstruct A Tree
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
pairs contains unique unordered relationships represented as [x,y] with x < y. Count rooted trees whose nodes are exactly the values appearing in pairs, where a pair is present if and only if one node is a proper ancestor of the other. The tree need not be binary. Trees differ when a parent assignment differs. Return 0 for no tree, 1 for exactly one, or 2 for multiple trees.
Source: Number Of Ways To Reconstruct A Tree on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
pairs = [[1,2],[2,3]]
1
Node 2 must be the root: it is the only node related to both other nodes. Put nodes 1 and 3 directly beneath it. This gives exactly the required ancestor relationships (1,2) and (2,3), while 1 and 3 remain unrelated siblings. Placing one beneath the other would introduce the absent pair (1,3). No other root can be an ancestor of every node without adding a missing pair, so exactly one rooted tree is possible.
# Example 2
pairs = [[1,2],[2,3],[1,3]]
2
Every pair of the three nodes must have an ancestor relationship, so all three must lie on one chain. Both 1 → 2 → 3 and 2 → 1 → 3 work, where an arrow points from parent to child; every other ordering also works. There are 3! = 6 distinct rooted chains. The required answer is nevertheless 2 because the API uses 2 to mean multiple possible trees, not exactly two. Pair order does not specify which member is the ancestor.
# Example 3
pairs = [[1,2],[2,3],[2,4],[1,5]]
0
The nodes are 1 through 5. In any rooted tree, its root is an ancestor of all four other nodes, so the pairs must include a relationship between that root and every other node. No candidate satisfies this: node 2 has only three listed neighbors, node 1 has two, and nodes 3, 4, and 5 each have one. A suitable root cannot exist, so return 0. The pairs describe all ancestor relationships, not merely parent-child edges; treating them as the edges of an ordinary tree would give the wrong conclusion.
Constraints
How to solve Number Of Ways To Reconstruct A Tree
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
A node's degree in the pair graph equals its number of ancestors plus descendants, so the root must touch every other node, and each other node's parent is its lowest-degree neighbor with degree at least its own; a node and parent with equal degree are interchangeable, which is the only source of multiple trees.
Why brute force is not enough
Trying every parent assignment for the m distinct nodes is m^(m-1) work, hopeless for up to 500 nodes, and treating the pairs as tree edges is wrong because they encode every ancestor relationship, not just parent-child links.
Approach
- Build adjacency sets and degrees; m is the number of distinct values that appear.
- Pick a node with degree m - 1 as the root; if none exists, return 0.
- For each other node x, choose as parent the neighbor with the smallest degree among neighbors whose degree is at least that of x.
- Verify every other neighbor of x is also a neighbor of that parent; any violation means return 0.
- If x and its parent have equal degree, note a tie; after all nodes pass, return 2 if any tie was noted, otherwise 1.
Walkthrough of Example 2
pairs = [[1,2],[2,3],[1,3]] → 2
- Nodes 1, 2, 3 each have degree 2 and m - 1 = 2, so a root exists; take node 1.
- Node 2 has neighbors 1 and 3, both of degree 2; node 1 becomes its parent with equal degree, so a tie is noted. Its other neighbor, 3, is adjacent to node 1, so verification passes.
- Node 3 has neighbors 1 and 2; node 1 is its parent with equal degree, another tie, and its other neighbor 2 is adjacent to node 1, so verification passes.
- No contradiction and a tie was noted, so return 2; the chains 1 over 2 over 3 and 1 over 3 over 2 both reproduce the pairs.
Time and space
Time O(P + m^2) · Space O(m^2). P is the number of pairs (up to 10^5) read once and m the number of distinct nodes (at most 500); each node's neighbor scan and subset check touch at most m entries using hash-set membership.
Interview pitfalls
- Choosing any higher-degree neighbor as the parent rather than the minimum-degree one at or above the node's degree; the parent is the nearest ancestor and has the smallest degree among them.
- Returning 2 as soon as a tie appears; a later subset failure must still produce 0.
- Including the parent itself in the subset check, which always fails because a node is not its own neighbor.
- Treating every id up to 500 as a node; only values that appear count toward m, and the root needs degree m - 1.
Follow-up questions interviewers ask
- How would you output one valid tree, and a second distinct one when the answer is 2?
- Can you count the exact number of valid trees instead of capping the answer at 2?
Related LeetCode Problems
Practice more problems similar to Number Of Ways To Reconstruct A Tree.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.