Find the Last Marked Nodes in Tree

Find the Last Marked Nodes in Tree

What is this problem about?

The Find the Last Marked Nodes in Tree interview question describes a unique marking process on an undirected tree. Starting from time $t=0$, nodes are marked according to their distance from initially chosen "seed" nodes. At each time step, unmarked neighbors of already marked nodes become marked. You are asked to find which nodes will be the very last to be marked across the entire tree.

Why is this asked in interviews?

Salesforce and other top-tier companies use this problem to test a candidate's mastery of Tree interview patterns and their ability to identify the "diameter" of a graph. The last nodes to be marked are always related to the farthest points in the tree. It evaluation whether you can reduce a complex temporal process to a fundamental property of trees: that the most distant node from any given node is always one of the endpoints of the tree's diameter.

Algorithmic pattern used

This problem relies on finding the Diameter of a Tree.

1. Find the two endpoints of the tree's diameter ($u$ and $v$). You can do this by running a BFS from an arbitrary node to find the farthest node ($u$), then a second BFS from $u$ to find the farthest node from it ($v$).
2. The "time" it takes for any node $i$ to be marked is determined by its distance to the farthest of these two endpoints: max(dist(i, u), dist(i, v)).
3. The "last marked" nodes are those whose distance to their farthest diameter endpoint is maximized.

Example explanation

Suppose we have a path-like tree: 0-1-2-3-4.

1. Endpoints of diameter: 0 and 4.
2. Distance from 2 to 0 is 2, distance from 2 to 4 is 2. Max = 2.
3. Distance from 0 to 4 is 4. Max = 4.
4. The nodes 0 and 4 will be the last marked if the marking started from the middle, or vice-versa. The logic depends on the specific starting condition, but the core remains the distance to diameter endpoints.

Common mistakes candidates make

• BFS for every node: Trying to calculate the distance from every node to every other node ($O(n^2)$), which is too slow for large trees.
• Ignoring Diameter: Failing to realize that in a tree, the farthest node from any point is always one of the diameter's ends.
• BFS/DFS implementation: Forgetting to handle the unweighted nature of tree edges correctly in the distance calculation.

Interview preparation tip

Practice the "Two-BFS" diameter algorithm. It is a standard trick for tree problems involving distances. If you need to find the "farthest node" for every single node in a tree, the diameter endpoints are almost always the keys to an $O(n)$ solution.