Skip to main content
Talentd

Time Taken to Mark All Nodes - Solution & Explanation

HardDynamic ProgrammingTreeDepth-First SearchGraph8 min read
Practice this problem

Problem Statement

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:

  • If 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.
  • If 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:

  • For i = 0:
    • Node 1 is marked at t = 1, and Node 2 at t = 2.
  • For i = 1:
    • Node 0 is marked at t = 2, and Node 2 at t = 4.
  • For i = 2:
    • Node 0 is marked at t = 2, and Node 1 at t = 3.

Example 2:

Input: edges = [[0,1]]

Output: [1,2]

Explanation:

  • For i = 0:
    • Node 1 is marked at t = 1.
  • For i = 1:
    • Node 0 is marked at t = 2.

Example 3:

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

Output: [4,6,3,5,5]

Explanation:

 

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • The input is generated such that edges represents a valid tree.

Approach Overview

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 1: Breadth-First Search (BFS)

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.

Code

PythonJavaScript

Python

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Depth-First Search (DFS)

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.

Code

JavaC++

Java

C++

Complexity

Time Complexity: O(n^2) due to iterative DFS from each node.
Space Complexity: O(n) for storing the graph and recursion stack.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Breadth-First Search (BFS)

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.

Depth-First Search (DFS)

Time Complexity: O(n^2) due to iterative DFS from each node.
Space Complexity: O(n) for storing the graph and recursion stack.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS from Every NodeO(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 OptimizationO(n)O(n)Best approach for large trees; calculates results for all starting nodes efficiently

Video Solution

A-D Leetcode Biweekly Contest 136 Editorials | Time Taken to Mark All Nodes | Abhinav Awasthi • Abhinav Awasthi • 6,639 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Time Taken to Mark All Nodes easy or hard?
Time Taken to Mark All Nodes is classified as a Hard problem because it combines tree traversal with rerooting dynamic programming. Recognizing that results for all roots can be computed in linear time using two DFS passes is the key challenge.
Time Taken to Mark All Nodes Python/Java solution
Python implementations commonly simulate the spread using BFS for clarity, while Java and C++ solutions often implement the optimized DFS rerooting dynamic programming approach. The optimal implementations run in O(n) time and store adjacency lists plus DP arrays.
How to solve Time Taken to Mark All Nodes in O(n)?
Use two DFS passes on the tree. The first DFS computes the maximum propagation time from each node to nodes in its subtree while accounting for the parity-based delay. The second DFS reroots the tree and updates distances so each node considers both its subtree paths and paths through its parent, producing the final answer for all nodes in linear time.
What is the best approach for Time Taken to Mark All Nodes?
The most efficient approach uses rerooting dynamic programming with depth-first search on the tree. First compute the longest propagation time inside each subtree, then reroot the tree to account for paths through the parent side. This allows calculating the marking time for every starting node in O(n) time and O(n) space.
Is Time Taken to Mark All Nodes asked at Google/Amazon/Meta?
Problems involving rerooting DP on trees and propagation across graphs frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this problem test understanding of tree dynamic programming, longest path calculations, and efficient graph traversal.
What data structure is used in Time Taken to Mark All Nodes?
The solution uses an adjacency list to represent the tree, along with DFS or BFS traversal. The optimized method also uses arrays to store dynamic programming values such as the longest propagation time in each subtree and rerooted results for every node.
What is the time complexity of Time Taken to Mark All Nodes?
The optimal solution runs in O(n) time using DFS-based tree dynamic programming with a rerooting technique. Each edge in the tree is processed a constant number of times. A straightforward BFS simulation from every node takes O(n²) time because the traversal is repeated for all possible starting nodes.

Ready to solve this problem?

Practice Time Taken to Mark All Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find the Last Marked Nodes in Tree

Next

Most Profitable Path in a Tree