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. After every second, you mark all unmarked nodes which have at least one marked node adjacent to them.
Return an array nodes where nodes[i] is the last node to get marked in the tree, if you mark node i at time t = 0. If nodes[i] has multiple answers for any node i, you can choose any one answer.
Example 1:
Input: edges = [[0,1],[0,2]]
Output: [2,2,1]
Explanation:
i = 0, the nodes are marked in the sequence: [0] -> [0,1,2]. Either 1 or 2 can be the answer.i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2]. Node 2 is marked last.i = 2, the nodes are marked in the sequence: [2] -> [0,2] -> [0,1,2]. Node 1 is marked last.Example 2:
Input: edges = [[0,1]]
Output: [1,0]
Explanation:
i = 0, the nodes are marked in the sequence: [0] -> [0,1].i = 1, the nodes are marked in the sequence: [1] -> [0,1].Example 3:
Input: edges = [[0,1],[0,2],[2,3],[2,4]]
Output: [3,3,1,1,1]
Explanation:
i = 0, the nodes are marked in the sequence: [0] -> [0,1,2] -> [0,1,2,3,4].i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2] -> [0,1,2,3,4].i = 2, the nodes are marked in the sequence: [2] -> [0,2,3,4] -> [0,1,2,3,4].i = 3, the nodes are marked in the sequence: [3] -> [2,3] -> [0,2,3,4] -> [0,1,2,3,4].i = 4, the nodes are marked in the sequence: [4] -> [2,4] -> [0,2,3,4] -> [0,1,2,3,4].
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 where some nodes are marked. For every node, determine which marked node would be the last one reached if a signal spreads through the tree edges one step at a time. In practice, this means finding the marked node with the maximum distance from each node.
Approach 1: Brute Force DFS from Every Node (O(n^2) time, O(n) space)
Treat each node as a starting point. Run a Depth-First Search or BFS to compute the distance to all other nodes, then pick the farthest node that is marked. Repeat this process for every node. The idea is straightforward: explore the entire tree and track the maximum distance to a marked node. However, because each traversal touches all n nodes, the total cost becomes O(n^2). This approach works for small trees but quickly becomes too slow for large inputs.
Approach 2: Multi-Source BFS from Marked Nodes (O(n) time, O(n) space)
Start a BFS simultaneously from all marked nodes using a queue. This computes the closest marked node for every node in the tree. While useful for proximity problems, it does not directly solve the "last marked" requirement because the farthest node matters, not the nearest one. You would need additional distance tracking or reverse reasoning to determine the farthest marked node. This method is helpful for understanding the structure of distances but is usually not the final optimized solution.
Approach 3: Tree Diameter of Marked Nodes + DFS (O(n) time, O(n) space)
The key observation: in a tree, the farthest node from any node must lie on the tree's diameter. If you restrict the diameter to marked nodes, the answer for any node must be one of the two endpoints of that diameter. First, run a DFS to find the farthest marked node from any marked node. Then run another DFS from that node to find the opposite endpoint of the marked diameter. Finally, compute distances from both endpoints using DFS. For each node, compare the distance to both endpoints and choose the farther one. This works because the longest path between marked nodes captures the extreme candidates.
This technique relies heavily on properties of trees and repeated DFS traversals. Each traversal is linear, and only a few passes over the adjacency list are needed.
Recommended for interviews: The diameter + DFS approach is what interviewers typically expect. Starting with the brute force method shows you understand the problem definition. Transitioning to the diameter insight demonstrates strong tree intuition and algorithmic optimization, reducing the complexity from O(n^2) to O(n).
According to the problem description, the last marked node must be one endpoint of the tree's diameter, because the distance from any node on the diameter to any other node on the diameter is the greatest.
We can start a depth-first search (DFS) from any node to find the farthest node a, which is one endpoint of the tree's diameter.
Then, starting from node a, we perform another depth-first search to find the farthest node b, which is the other endpoint of the tree's diameter. During this process, we calculate the distance from each node to node a, denoted as dist2.
Next, we perform a depth-first search starting from node b to calculate the distance from each node to node b, denoted as dist3.
For each node i, if dist2[i] > dist3[i], then the distance from node a to node i is greater, so node a is the last marked node; otherwise, node b is the last marked node.
The time complexity is O(n), and the space complexity is O(n). Here, n$ is the number of nodes.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force DFS from Every Node | O(n^2) | O(n) | Small trees or when first reasoning about the problem |
| Multi-Source BFS from Marked Nodes | O(n) | O(n) | Useful for analyzing distance structure or nearest-marked queries |
| Diameter of Marked Nodes + DFS | O(n) | O(n) | Optimal solution for large trees and interview settings |
Lowest Common Ancestor of a Binary Search Tree - Leetcode 235 - Python • NeetCode • 274,690 views views
Watch 9 more video solutions →Practice Find the Last Marked Nodes in Tree with our built-in code editor and test cases.
Practice on FleetCode