Watch 8 video solutions for Count Number of Possible Root Nodes, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by A Code Daily! has 2,167 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Alice has an undirected tree with n nodes labeled from 0 to n - 1. The tree is represented as a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Alice wants Bob to find the root of the tree. She allows Bob to make several guesses about her tree. In one guess, he does the following:
u and v such that there exists an edge [u, v] in the tree.u is the parent of v in the tree.Bob's guesses are represented by a 2D integer array guesses where guesses[j] = [uj, vj] indicates Bob guessed uj to be the parent of vj.
Alice being lazy, does not reply to each of Bob's guesses, but just says that at least k of his guesses are true.
Given the 2D integer arrays edges, guesses and the integer k, return the number of possible nodes that can be the root of Alice's tree. If there is no such tree, return 0.
Example 1:
Input: edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3 Output: 3 Explanation: Root = 0, correct guesses = [1,3], [0,1], [2,4] Root = 1, correct guesses = [1,3], [1,0], [2,4] Root = 2, correct guesses = [1,3], [1,0], [2,4] Root = 3, correct guesses = [1,0], [2,4] Root = 4, correct guesses = [1,3], [1,0] Considering 0, 1, or 2 as root node leads to 3 correct guesses.
Example 2:
Input: edges = [[0,1],[1,2],[2,3],[3,4]], guesses = [[1,0],[3,4],[2,1],[3,2]], k = 1 Output: 5 Explanation: Root = 0, correct guesses = [3,4] Root = 1, correct guesses = [1,0], [3,4] Root = 2, correct guesses = [1,0], [2,1], [3,4] Root = 3, correct guesses = [1,0], [2,1], [3,2], [3,4] Root = 4, correct guesses = [1,0], [2,1], [3,2] Considering any node as root will give at least 1 correct guess.
Constraints:
edges.length == n - 12 <= n <= 1051 <= guesses.length <= 1050 <= ai, bi, uj, vj <= n - 1ai != biuj != vjedges represents a valid tree.guesses[j] is an edge of the tree.guesses is unique.0 <= k <= guesses.lengthProblem Overview: You are given an undirected tree with n nodes and a list of parent-child guesses. A guess (u, v) means someone believes u is the parent of v. For a chosen root, the tree becomes directed from parent to child. The task is to count how many nodes could be valid roots such that at least k guesses become correct.
Approach 1: Depth-First Search with Rerooting (O(n))
Store all guesses in a HashSet for constant-time lookup. First root the tree at node 0 and run a Depth-First Search to count how many guesses match the parent-child direction. Each DFS step checks whether (parent, child) exists in the guess set. This gives the number of correct guesses if the root is 0. Next, reroot the tree using a second DFS: when moving the root from u to v, adjust the score by subtracting (u, v) if it was a correct guess and adding (v, u) if that guess exists. This rerooting trick reuses previous computation instead of recomputing from scratch.
The key insight: changing the root only affects the orientation of one edge. Maintaining the score incrementally avoids repeating full traversals. Using adjacency lists for the tree and a hash table for guesses keeps operations constant time. Total complexity is O(n) time and O(n) space.
Approach 2: Union-Find (Disjoint Set Union) Assisted Validation (O(n α(n)))
Union-Find can be used to manage connectivity while evaluating potential parent-child relationships implied by guesses. Build the tree using adjacency lists, then use DSU to ensure edges belong to the same connected component and to quickly verify relationships when testing possible roots. For each node treated as root, validate guess directions along the tree structure while relying on DSU to avoid repeated connectivity checks. This reduces structural overhead but still requires traversing edges for orientation validation.
This method runs in roughly O(n α(n)) time due to near-constant amortized union/find operations and uses O(n) space. It is less common for interviews but can simplify connectivity reasoning when combining multiple structural constraints.
Recommended for interviews: The DFS rerooting approach is the expected solution. Start by computing correct guesses for a fixed root, then apply reroot dynamic programming to update counts in constant time per edge. This demonstrates strong understanding of tree rerooting DP and efficient graph traversal. A brute-force attempt (testing every node as root with full DFS) shows baseline reasoning but runs in O(n²), which is too slow for large inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force: Try Every Node as Root with DFS | O(n²) | O(n) | Conceptual baseline or very small trees |
| DFS with Rerooting and Guess HashSet | O(n) | O(n) | Optimal approach for interviews and large inputs |
| Union-Find Assisted Validation | O(n α(n)) | O(n) | When combining connectivity checks with structural constraints |