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.
This approach involves building the tree and performing a Depth-First Search (DFS) from an arbitrary node, usually node 0, to determine the initial configuration or parent-child relationships. By maintaining awareness of which guesses match the found parent-child relationships, you can compute the number of valid roots by rerooting the tree at each node.
The C implementation uses basic adjacency matrix to represent the tree graph. DFS is implemented to explore and calculate valid guesses for each node treated as the root. The counter is incremented when a node u and its child v is correctly guessed according to the given guesses. Resetting the visited array and guess count for each node ensures correctness.
Time Complexity: O(n^2), where n is the number of nodes. This results from the DFS implementation using an adjacency matrix, which inefficiently checks each potential connection.
Space Complexity: O(n^2), due to the adjacency matrix used for graph representation.
This approach utilizes the Union-Find data structure to keep track of connected components in an efficient way—each node as its own separate component and merging them via edges. By adapting the structure for parent relationships and examining which parent associations hold true, we can determine potential roots that meet the guessing criteria.
The Union-Find approach involves an initial setup of disjoint sets with each node as its own component. Union operations merge components represented by the edges. For guesses, their validity is checked by finding their roots, allowing accumulation of correct guess counts. Nodes with a correct count greater than or equal to k will be marked as valid roots.
Time Complexity: O(n*α(n)), where α is the inverse Ackermann function, due to the efficient union-find operations.
Space Complexity: O(n), for storing parent and rank arrays.
First, we traverse the given edge set edges and convert it to an adjacency list g where g[i] represents the adjacent nodes of node i. Use a hash map gs to record the given guess set guesses.
Then, we start from node 0 and perform a DFS to count the number of edges in guesses among all the nodes that can be reached from node 0. We use the variable cnt to record this number.
Next, we start from node 0 and perform a DFS to count the number of edges in guesses in each tree with 0 as the root. If the number is greater than or equal to k, it means that this node is a possible root node, and we add 1 to the answer.
Therefore, the problem becomes to count the number of edges in guesses in each tree with each node as the root. We already know that there are cnt edges in guesses among all the nodes that can be reached from node 0. We can maintain this value by adding or subtracting the current edge in guesses in DFS.
Assume that we are currently traversing node i and cnt represents the number of edges in guesses with i as the root node. Then, for each adjacent node j of i, we need to calculate the number of edges in guesses with j as the root node. If (i, j) is in guesses, then there is no edge (i, j) in the tree with j as the root node, so cnt should decrease by 1. If (j, i) is in guesses, then there is an extra edge (i, j) in the tree with j as the root node, so cnt should increase by 1. That is, f[j] = f[i] + (j, i) \in guesses - (i, j) \in guesses. Where f[i] represents the number of edges in guesses with i as the root node.
The time complexity is O(n + m) and the space complexity is O(n + m), where n and m are the lengths of edges and guesses respectively.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Depth-First Search (DFS) with Rooted Tree | Time Complexity: O(n^2), where n is the number of nodes. This results from the DFS implementation using an adjacency matrix, which inefficiently checks each potential connection. Space Complexity: O(n^2), due to the adjacency matrix used for graph representation. |
| Using Union-Find (Disjoint Set Union, DSU) | Time Complexity: O(n*α(n)), where α is the inverse Ackermann function, due to the efficient union-find operations. |
| Tree DP (change root) | — |
| 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 |
Count Number of Possible Root Nodes | Tree rerooting | Leetcode 2581| Discord live session • A Code Daily! • 2,167 views views
Watch 7 more video solutions →Practice Count Number of Possible Root Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor