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.
This approach utilizes a Breadth-First Search (BFS) traversal to determine the time it takes to mark all nodes. By starting from the node i and considering the marking rules based on node parity (odd or even), we propagate markings across the tree. Utilize a queue to manage nodes to be visited and a distance array to track marking times.
In this Python solution, we maintain a graph representation of the tree using adjacency lists. For each node, marked as the starting point, perform a BFS to calculate the time it takes to mark all other nodes considering their conditions. This way, distances from the starting node to others are incrementally updated.
Python
JavaScript
Time Complexity: O(n^2) since for each node we perform a BFS which could traverse all nodes.
Space Complexity: O(n) for storing the graph and the queue in BFS.
This approach uses Depth-First Search (DFS) to traverse the tree and recursively calculate the time to mark nodes based on their conditions. It ensures that nodes are visited according to their marking rules, and marking times are dynamically computed and updated.
In the Java solution, we represent the tree using adjacency lists. A DFS is performed for each node, accounting for marking rules by adjusting the timing of nodes recursively based on their even or odd indices, thus producing the maximum marking time from any given starting node.
Time Complexity: O(n^2) due to iterative DFS from each node.
Space Complexity: O(n) for storing the graph and recursion stack.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | Time Complexity: O(n^2) since for each node we perform a BFS which could traverse all nodes. |
| Depth-First Search (DFS) | Time Complexity: O(n^2) due to iterative DFS from each node. |
| 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 |
A-D Leetcode Biweekly Contest 136 Editorials | Time Taken to Mark All Nodes | Abhinav Awasthi • Abhinav Awasthi • 6,552 views views
Watch 6 more video solutions →Practice Time Taken to Mark All Nodes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor