Watch 7 video solutions for Time Taken to Mark All Nodes, a hard level problem involving Dynamic Programming, Tree, Depth-First Search. This walkthrough by Abhinav Awasthi has 6,552 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [ui, vi] indicates that there is an edge between nodes ui and vi in the tree.
Initially, all nodes are unmarked. For each node i:
i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.
Note that the answer for each times[i] is independent, i.e. when you mark node i all other nodes are unmarked.
Example 1:
Input: edges = [[0,1],[0,2]]
Output: [2,4,3]
Explanation:
i = 0:
t = 1, and Node 2 at t = 2.i = 1:
t = 2, and Node 2 at t = 4.i = 2:
t = 2, and Node 1 at t = 3.Example 2:
Input: edges = [[0,1]]
Output: [1,2]
Explanation:
i = 0:
t = 1.i = 1:
t = 2.Example 3:
Input: edges = [[2,4],[0,1],[2,3],[0,2]]
Output: [4,6,3,5,5]
Explanation:
Constraints:
2 <= n <= 105edges.length == n - 1edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges represents a valid tree.Problem Overview: You are given a tree with n nodes. If a node becomes marked, it spreads the mark to its neighbors after a delay that depends on the node’s parity (odd nodes propagate faster than even nodes). For every node i, treat it as the starting node and compute how long it takes until all nodes in the tree are marked.
Approach 1: Breadth-First Search from Every Node (BFS) (Time: O(n²), Space: O(n))
Build an adjacency list for the tree and run BFS starting from each node. The BFS simulates how the mark spreads through the graph. When visiting a neighbor, add a delay based on the node’s parity (for example, +1 for odd nodes and +2 for even nodes). Track the maximum time required to reach any node during that traversal. Repeating this process for all n starting nodes produces the final answer array. This approach is straightforward and mirrors the spreading process directly, but it recomputes traversal work for every root, which leads to quadratic complexity on large trees.
Approach 2: Rerooting with Depth-First Search (DFS) + Dynamic Programming (Time: O(n), Space: O(n))
The optimal approach uses dynamic programming on a tree combined with depth-first search. First run a DFS to compute the longest time needed to reach descendants for every node (a "down" value). Each transition adds the parity-based delay for the destination node. This gives the maximum marking time within each node’s subtree.
A second DFS performs a rerooting step. When moving the root from a parent to a child, recompute the maximum distance considering both the child’s subtree and paths that go upward through the parent. Maintain the two largest child contributions so you can update values efficiently when excluding a specific branch. The final result for node i is the maximum time required to reach any node in the tree when the spread starts from i. Because each edge is processed a constant number of times, the total complexity remains linear.
Recommended for interviews: Start by explaining the BFS simulation since it directly models the marking process and shows clear understanding of graph traversal. Interviewers usually expect the rerooting DFS optimization. It reduces repeated work by turning the problem into a classic tree DP that computes distances for every possible root in O(n) time.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| BFS from Every Node | O(n²) | O(n) | Useful for understanding the marking spread simulation or when n is small |
| DFS Tree DP (Subtree Distances) | O(n) | O(n) | Computes longest downward propagation times in each subtree |
| Rerooting DFS Optimization | O(n) | O(n) | Best approach for large trees; calculates results for all starting nodes efficiently |