Count Number of Possible Root Nodes

Count Number of Possible Root Nodes

What is this problem about?

You are given an undirected tree and a set of "guesses" where each guess is a directed edge $(u, v)$ meaning $u$ is a parent of $v$ in the rooted tree. A node is a "possible root" if, when the tree is rooted at that node, at least $k$ guesses are correct. You need to count how many such possible root nodes exist.

Why is this asked in interviews?

Google uses this "Hard" problem to test a candidate's mastery of the Re-rooting technique in Dynamic Programming on Trees. It requires you to calculate a property for one root and then efficiently update that property as you "move" the root to adjacent nodes. This avoids the $O(n^2)$ trap of running a full DFS for every possible root.

Algorithmic pattern used

The pattern is DFS with Re-rooting (also known as the "Rerooting DP" pattern).

1. Root the tree arbitrarily (e.g., at node 0) and use DFS to count how many guesses are correct for this initial root. Store the set of guesses in a Hash Set for $O(1)$ lookup.
2. Perform a second DFS to traverse the tree. When moving the root from node $u$ to an adjacent child $v$:
   • If the guess $(u, v)$ existed, it is no longer correct (decrement count).
   • If the guess $(v, u)$ existed, it is now correct (increment count).
3. If the count at node $v$ is $\ge k$, it is a valid root.

Example explanation

Tree: 0-1, Guesses: (0, 1), (1, 0), $k = 1$.

1. Root at 0: Guess (0, 1) is correct. Count = 1. $\ge k$, so 0 is a valid root.
2. Move root to 1:
   • Guess (0, 1) becomes incorrect (1 is now parent of 0). Count: $1 - 1 = 0$.
   • Guess (1, 0) becomes correct. Count: $0 + 1 = 1$.
   • $\ge k$, so 1 is also a valid root. Total valid roots: 2.

Common mistakes candidates make

The biggest mistake is attempting to root the tree at every node and run a full DFS each time, resulting in $O(n imes (n+g))$ which is too slow. Another error is not correctly identifying how a guess "flips" when the parent-child relationship is reversed. Using a set for guesses is also crucial for performance.

Interview preparation tip

Study the "Re-rooting DP" pattern. It is the gold standard for tree problems where you need to calculate a global property for every single node. The key is always to identify what information is lost and what is gained when an edge is "flipped."