Find the Last Marked Nodes in Tree - Practice Coding Problems

Find the Last Marked Nodes in Tree - Problem

Imagine a viral spread simulation on a tree network! You have an undirected tree with n nodes numbered from 0 to n-1, connected by n-1 edges.

Here's how the simulation works:

At time t = 0, you mark exactly one node as the initial infection source
Every second after that, the infection spreads to all unmarked nodes that are adjacent to any already marked node
This continues until every node in the tree is marked

Your task: For each possible starting node i, determine which node will be the very last to get marked. Return an array where result[i] is the last node to be marked when starting from node i.

Note: If there are multiple nodes that could be last (tied for the same time), you can return any of them.

Input & Output

example_1.py — Basic Tree

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

› Output: [3, 3, 3, 3]

💡 Note: Tree: 2-0-1-3. Starting from any node, node 3 is always the farthest (or tied for farthest), so it gets marked last in all cases.

example_2.py — Linear Tree

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

› Output: [4, 4, 4, 0, 0]

💡 Note: Linear tree: 0-1-2-3-4. When starting from nodes 0,1,2, node 4 is farthest. When starting from nodes 3,4, node 0 is farthest.

example_3.py — Single Node

$ Input: edges = []

› Output: [0]

💡 Note: Only one node exists (node 0), so when starting from node 0, node 0 itself is the last (and only) node to be marked.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
0 ≤ u_i, v_i < n
The input represents a valid tree (connected and acyclic)

Visualization

Tap to expand

Understanding the Visualization

Initialize

Mark the starting node at time t=0

Wave 1

At t=1, mark all direct neighbors of initially marked nodes

Wave 2+

Continue marking neighbors of newly marked nodes each second

Final Wave

The last wave contains the final node(s) to be marked

Key Takeaway

🎯 Key Insight: The marking process spreads in waves like a breadth-first search. The last node to be marked is always at the maximum distance from the starting point, which corresponds to one of the tree's diameter endpoints!

Asked in

G Google 28 a Amazon 22 f Meta 15 ⊞ Microsoft 12

The key insight is that the last marked node is always at maximum distance from the starting node. In trees, nodes at maximum distance are always diameter endpoints. The optimal approach finds the tree's diameter using two BFS passes, then for each starting node, determines which diameter endpoint is farther away.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (BFS Simulation)	O(n²)	O(n)	Simulate the marking process for each starting node using BFS
Two-Pass Tree Diameter	O(n²)	O(n)	Find tree diameter in two BFS passes, then determine farthest endpoint for each node

Brute Force (BFS Simulation) — Algorithm Steps

For each node i from 0 to n-1 as starting point
Run BFS from node i, marking nodes level by level
Track the order in which nodes get marked
The last node marked in this BFS is the answer for starting node i
Store this result and repeat for next starting node

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Starting Node

Select node i as the initial marked node

BFS Level 1

Mark all direct neighbors of the starting node

BFS Level 2+

Continue marking neighbors level by level until all nodes are marked

Record Last Node

The last node marked in this BFS is the answer for starting node i

Code -

solution.c — C

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

#define MAX_N 1000

int graph[MAX_N][MAX_N];
int degree[MAX_N];
int queue[MAX_N];
bool visited[MAX_N];

int* findLastMarkedNodes(int** edges, int edgesSize, int n) {
    int* result = (int*)malloc(n * sizeof(int));
    
    // Initialize graph
    for (int i = 0; i < n; i++) {
        degree[i] = 0;
        for (int j = 0; j < n; j++) {
            graph[i][j] = 0;
        }
    }
    
    // Build adjacency list
    for (int i = 0; i < edgesSize; i++) {
        int u = edges[i][0], v = edges[i][1];
        graph[u][degree[u]++] = v;
        graph[v][degree[v]++] = u;
    }
    
    // For each starting node
    for (int start = 0; start < n; start++) {
        // Reset visited array
        for (int i = 0; i < n; i++) visited[i] = false;
        
        // BFS simulation
        int front = 0, rear = 0;
        queue[rear++] = start;
        visited[start] = true;
        int lastMarked = start;
        
        while (front < rear) {
            int levelSize = rear - front;
            for (int i = 0; i < levelSize; i++) {
                int node = queue[front++];
                lastMarked = node;
                
                // Add unvisited neighbors
                for (int j = 0; j < degree[node]; j++) {
                    int neighbor = graph[node][j];
                    if (!visited[neighbor]) {
                        visited[neighbor] = true;
                        queue[rear++] = neighbor;
                    }
                }
            }
        }
        
        result[start] = lastMarked;
    }
    
    return result;
}

int main() {
    int edges[][2] = {{0,1},{0,2},{1,3}};
    int* edgePointers[] = {edges[0], edges[1], edges[2]};
    int n = 4, edgesSize = 3;
    
    int* result = findLastMarkedNodes(edgePointers, edgesSize, n);
    for (int i = 0; i < n; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

We run BFS for each of n starting nodes, and each BFS takes O(n) time

⚠ Quadratic Growth

Space Complexity

O(n)

BFS queue can hold up to O(n) nodes, plus adjacency list storage

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~25 min Avg. Time

890 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

Brute Force (BFS Simulation) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler