Watch 10 video solutions for Find the Last Marked Nodes in Tree, a hard level problem involving Tree, Depth-First Search. This walkthrough by NeetCode has 274,690 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. 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).
| 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 |