Amount of Time for Binary Tree to Be Infected

Amount of Time for Binary Tree to Be Infected - Problem

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Each minute, a node becomes infected if:

The node is currently uninfected.
The node is adjacent to an infected node.

Return the number of minutes needed for the entire tree to be infected.

Input & Output

Example 1 — Basic Tree Infection

$ Input: root = [1,5,3,null,4,10,6,null,null,9,2], start = 3

› Output: 4

💡 Note: At minute 0, node 3 is infected. At minute 1, nodes 1 and 10 and 6 become infected. At minute 2, node 5 becomes infected. At minute 3, node 4 becomes infected. At minute 4, nodes 9 and 2 become infected. Total time: 4 minutes.

Example 2 — Single Node

$ Input: root = [1], start = 1

› Output: 0

💡 Note: Only one node in the tree, so it takes 0 minutes to infect the entire tree.

Example 3 — Start from Leaf

$ Input: root = [1,2,3,4,5], start = 4

› Output: 3

💡 Note: Starting from leaf node 4, it takes 3 minutes to reach the farthest node on the other side of the tree.

Constraints

The number of nodes in the tree is in the range [1, 10⁵].
1 ≤ Node.val ≤ 10⁵
Each node has a unique value.
A node with a value of start exists in the tree.

Visualization

Tap to expand

Understanding the Visualization

Initial State

Tree with infection starting at specified node

Spread Process

Infection spreads to adjacent nodes each minute

Complete Infection

Time when last node becomes infected

Key Takeaway

🎯 Key Insight: Convert the tree to a graph and use BFS to simulate infection spread level by level

Asked in

F Facebook 35 a Amazon 28 M Microsoft 22 G Google 18

The key insight is to treat the binary tree as an undirected graph where infection spreads to adjacent nodes each minute. Best approach is BFS graph conversion which builds an adjacency list and simulates infection spread level by level. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ BFS Graph Conversion	O(n)	O(n)	Convert tree to graph, then BFS from start node to find maximum distance
Brute Force - Find All Distances	O(n²)	O(n)	Calculate distance from start node to every other node, return maximum

BFS Graph Conversion — Algorithm Steps

Convert binary tree to adjacency list
Start BFS from the infected node
Count levels until all nodes are visited

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Convert tree to adjacency list

BFS Traversal

Visit nodes level by level from start

Count Levels

Each level represents one minute

Code -

solution.c — C

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

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void buildGraph(struct TreeNode* node, int graph[][100], int* graphSize, struct TreeNode* parent) {
    if (!node) return;
    if (parent) {
        graph[node->val][graphSize[node->val]++] = parent->val;
        graph[parent->val][graphSize[parent->val]++] = node->val;
    }
    buildGraph(node->left, graph, graphSize, node);
    buildGraph(node->right, graph, graphSize, node);
}

int solution(struct TreeNode* root, int start) {
    if (!root) return 0;
    
    int graph[100][100];
    int graphSize[100] = {0};
    buildGraph(root, graph, graphSize, NULL);
    
    int queue[1000];
    int front = 0, rear = 0;
    int visited[100] = {0};
    queue[rear++] = start;
    visited[start] = 1;
    int time = 0;
    
    while (front < rear) {
        int size = rear - front;
        for (int i = 0; i < size; i++) {
            int node = queue[front++];
            for (int j = 0; j < graphSize[node]; j++) {
                int neighbor = graph[node][j];
                if (!visited[neighbor]) {
                    visited[neighbor] = 1;
                    queue[rear++] = neighbor;
                }
            }
        }
        if (front < rear) {
            time++;
        }
    }
    
    return time;
}

struct TreeNode* buildTree(int* arr, int size) {
    if (size == 0) return NULL;
    struct TreeNode* root = createNode(arr[0]);
    struct TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    
    int i = 1;
    while (front < rear && i < size) {
        struct TreeNode* node = queue[front++];
        if (i < size && arr[i] != -1) {
            node->left = createNode(arr[i]);
            queue[rear++] = node->left;
        }
        i++;
        if (i < size && arr[i] != -1) {
            node->right = createNode(arr[i]);
            queue[rear++] = node->right;
        }
        i++;
    }
    return root;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (strstr(token, "null") == NULL) {
            arr[size++] = atoi(token);
        } else {
            arr[size++] = -1;
        }
        token = strtok(NULL, "[,]");
    }
    
    int start;
    scanf("%d", &start);
    
    struct TreeNode* root = buildTree(arr, size);
    printf("%d\n", solution(root, start));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to build graph O(n) + BFS visits each node once O(n)

✓ Linear Growth

Space Complexity

O(n)

Adjacency list stores all edges (n-1 edges, each stored twice) + BFS queue

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

892 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

BFS Graph Conversion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler