Count Number of Possible Root Nodes - Practice Coding Problems

Count Number of Possible Root Nodes - Problem

Array Hash Table Dynamic Programming Tree Depth-First Search Hard

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:

Chooses two distinct integers u and v such that there exists an edge [u, v] in the tree.
He tells Alice that 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.

Input & Output

Example 1 — Basic Tree

$ Input: edges = [[0,1],[1,2],[1,3],[4,2]], guesses = [[1,3],[0,1],[1,0],[2,4]], k = 3

› Output: 3

💡 Note: Tree has 5 nodes. Testing different roots: root 0 has 1 correct guess, root 1 has 3 correct guesses, root 2 has 3 correct guesses, others have fewer. So 3 possible roots meet k=3 requirement.

Example 2 — Small Tree

$ Input: edges = [[0,1],[0,2]], guesses = [[0,1]], k = 1

› Output: 2

💡 Note: Simple tree with 3 nodes. Root 0 has 1 correct guess [0,1]. Root 1 or 2 as root would have 0 correct guesses. So 1 root meets k=1.

Example 3 — No Valid Root

$ Input: edges = [[0,1]], guesses = [[1,0]], k = 2

› Output: 0

💡 Note: Only 2 nodes connected. At most 1 guess can be correct for any root, but k=2 requires at least 2 correct guesses. No valid root exists.

Constraints

n == edges.length + 1
1 ≤ n ≤ 10⁵
1 ≤ guesses.length ≤ 10⁵
0 ≤ k ≤ guesses.length

Visualization

Tap to expand

Understanding the Visualization

Input

Tree edges and Bob's parent-child guesses with threshold k

Process

For each possible root, count matching parent-child relationships

Output

Number of roots where correct guesses ≥ k

Key Takeaway

🎯 Key Insight: Use tree rerooting DP to efficiently calculate correct guesses for all possible roots in O(n) time instead of O(n²) brute force

Asked in

G Google 15 f Facebook 12

The key insight is using tree rerooting to efficiently calculate correct guesses for all possible roots. Instead of rebuilding the tree for each root candidate, we start with one root and use dynamic programming to update the count when moving the root to adjacent nodes. Best approach uses tree rerooting DP with Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Tree Rerooting - Single Pass	O(n)	O(n)	Use tree rerooting to efficiently calculate correct guesses for all possible roots
Brute Force - Try Each Root	O(n²)	O(n)	For each possible root, build the rooted tree and count correct guesses

Tree Rerooting - Single Pass — Algorithm Steps

Pick arbitrary root and count correct guesses with DFS
For each edge, calculate how count changes when moving root
Use rerooting DP to propagate changes across the tree
Count roots where correct guesses >= k

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial Root

Start with root 0 and count correct guesses

Reroot

Move root to adjacent node and update count

Propagate

Continue rerooting to cover all possible roots

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_N 1005

struct Edge {
    int to;
    struct Edge* next;
};

struct Graph {
    struct Edge* adj[MAX_N];
    int n;
};

struct Guess {
    int u, v;
};

int result = 0;

void addEdge(struct Graph* g, int u, int v) {
    struct Edge* e = malloc(sizeof(struct Edge));
    e->to = v;
    e->next = g->adj[u];
    g->adj[u] = e;
}

bool hasGuess(struct Guess* guesses, int guessCount, int u, int v) {
    for (int i = 0; i < guessCount; i++) {
        if (guesses[i].u == u && guesses[i].v == v) {
            return true;
        }
    }
    return false;
}

int dfs1(struct Graph* g, int node, int parent, struct Guess* guesses, int guessCount) {
    int correct = 0;
    if (parent != -1 && hasGuess(guesses, guessCount, parent, node)) {
        correct++;
    }
    
    struct Edge* e = g->adj[node];
    while (e) {
        if (e->to != parent) {
            correct += dfs1(g, e->to, node, guesses, guessCount);
        }
        e = e->next;
    }
    
    return correct;
}

void dfs2(struct Graph* g, int node, int parent, int correctCount, struct Guess* guesses, int guessCount, int k) {
    if (correctCount >= k) {
        result++;
    }
    
    struct Edge* e = g->adj[node];
    while (e) {
        if (e->to != parent) {
            // Calculate new correct count when moving root from node to neighbor
            int newCorrect = correctCount;
            
            // If guess (node, neighbor) exists, it becomes incorrect
            if (hasGuess(guesses, guessCount, node, e->to)) {
                newCorrect--;
            }
            
            // If guess (neighbor, node) exists, it becomes correct
            if (hasGuess(guesses, guessCount, e->to, node)) {
                newCorrect++;
            }
            
            dfs2(g, e->to, node, newCorrect, guesses, guessCount, k);
        }
        e = e->next;
    }
}

int solution(int edges[][2], int edgeCount, int guesses[][2], int guessCount, int k) {
    int n = edgeCount + 1;
    struct Graph g = {0};
    g.n = n;
    
    // Build adjacency list
    for (int i = 0; i < edgeCount; i++) {
        addEdge(&g, edges[i][0], edges[i][1]);
        addEdge(&g, edges[i][1], edges[i][0]);
    }
    
    // Convert guesses to struct array
    struct Guess* guessArray = malloc(guessCount * sizeof(struct Guess));
    for (int i = 0; i < guessCount; i++) {
        guessArray[i].u = guesses[i][0];
        guessArray[i].v = guesses[i][1];
    }
    
    // Count correct guesses for root 0
    int initialCorrect = dfs1(&g, 0, -1, guessArray, guessCount);
    
    // Reroot and count valid roots
    result = 0;
    dfs2(&g, 0, -1, initialCorrect, guessArray, guessCount, k);
    
    free(guessArray);
    return result;
}

int main() {
    // Simple parsing for basic test cases
    int edges[MAX_N][2], guesses[MAX_N][2];
    int edgeCount = 0, guessCount = 0, k = 0;
    
    // Read input manually for simplicity
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Parse edges array
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                edges[edgeCount][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                if (*ptr == ',') ptr++;
                edges[edgeCount][1] = atoi(ptr);
                edgeCount++;
                while (*ptr && *ptr != ']') ptr++;
                if (*ptr == ']') ptr++;
            }
            ptr++;
        }
    }
    
    fgets(line, sizeof(line), stdin);
    // Parse guesses array similarly
    ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                guesses[guessCount][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                if (*ptr == ',') ptr++;
                guesses[guessCount][1] = atoi(ptr);
                guessCount++;
                while (*ptr && *ptr != ']') ptr++;
                if (*ptr == ']') ptr++;
            }
            ptr++;
        }
    }
    
    fgets(line, sizeof(line), stdin);
    k = atoi(line);
    
    printf("%d\n", solution(edges, edgeCount, guesses, guessCount, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS to count initial guesses, then O(n) rerooting to calculate all roots

✓ Linear Growth

Space Complexity

O(n)

Adjacency list and recursion stack for tree traversal

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

324 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Tree Rerooting - Single Pass — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler