3313. Find the Last Marked Nodes in Tree 🔒
Problem Description
You have an undirected tree with n
nodes labeled from 0
to n - 1
. The tree structure is given through an array edges
of length n - 1
, where each edges[i] = [ui, vi]
represents an edge connecting nodes ui
and vi
.
The problem involves a marking process that works as follows:
- Initially, all nodes in the tree are unmarked
- You start by marking exactly one node at time
t = 0
- Every second after that, any unmarked node that has at least one marked neighbor becomes marked
- This process continues until all nodes are marked
Your task is to determine, for each possible starting node i
, which node would be the last one to get marked if you began the marking process from node i
.
The output should be an array nodes
where nodes[i]
represents the last node to be marked when starting from node i
. If there are multiple nodes that get marked at the same final time (multiple valid answers), you can return any one of them.
For example, if you start marking from a node near one end of a long path in the tree, the last node to be marked would likely be at the opposite end, as the marking would spread outward from your starting point like a wave, reaching the farthest nodes last.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: The problem explicitly mentions an undirected tree with nodes and edges. A tree is a special type of graph (connected and acyclic).
Is it a tree?
- Yes: The problem clearly states we have an undirected tree with
n
nodes andn-1
edges, which is the definition of a tree structure.
DFS
- Yes: We arrive at DFS as the recommended approach for tree problems.
Conclusion: The flowchart suggests using DFS (Depth-First Search) for this tree problem.
Why DFS is the Right Choice
The DFS pattern fits perfectly for this problem because:
-
Tree Traversal: We need to traverse the tree to find distances between nodes, which DFS handles efficiently.
-
Finding the Diameter: The solution requires finding the tree's diameter (the longest path between any two nodes). This is a classic DFS application where we:
- Start DFS from any node to find the farthest node (one endpoint of the diameter)
- Run DFS from that endpoint to find the other endpoint
- Calculate distances from both endpoints to all other nodes
-
Distance Calculation: DFS naturally calculates distances from a source node to all other nodes in a tree by tracking the depth/distance as we traverse.
-
Multiple Traversals: The solution requires multiple DFS traversals (three in total) to gather all necessary distance information, which DFS handles with O(n) time complexity per traversal.
The marking process described in the problem essentially spreads from the starting node to the farthest reachable node, and the endpoints of the tree's diameter are guaranteed to be the farthest nodes from any starting position, making DFS the ideal algorithm for solving this problem.
Intuition
Let's think about what happens when we start marking from any node. The marking spreads outward like a ripple in water - each second, the marking advances exactly one edge further from all currently marked nodes. This means the last node to be marked will be the one that's farthest away from our starting point.
Now here's the key insight: for any starting node in a tree, which node would be farthest away? It must be one of the endpoints of the tree's diameter (the longest path in the tree). Why? Because the diameter endpoints are, by definition, the two nodes that are maximally far apart in the entire tree.
Consider this: if you start from any node that's not on the diameter, you'll eventually reach the diameter and then need to traverse to one of its endpoints. But if you start from a node on the diameter, you'll still end up reaching one of the endpoints last. This is because the diameter represents the "longest stretch" in the tree.
Here's where it gets interesting - we don't need to compute the answer for each starting node independently. Since the last marked node must always be one of the two diameter endpoints, we only need to:
- Find both endpoints of the diameter (let's call them
a
andb
) - For each starting node
i
, determine which endpoint (a
orb
) is farther from it
To find the diameter endpoints, we use a well-known property: if we start a DFS from any node, the farthest node we reach is guaranteed to be one endpoint of the diameter. Then, if we start another DFS from that endpoint, the farthest node we reach is the other endpoint.
Once we have both endpoints a
and b
, we compute the distance from each node to both endpoints. For any starting node i
, if dist[i][a] > dist[i][b]
, then a
is farther and will be marked last; otherwise, b
will be marked last.
This elegant approach reduces what seems like an O(n²)
problem (computing the farthest node for each starting point) to just O(n)
with three DFS traversals.
Learn more about Tree and Depth-First Search patterns.
Solution Approach
The implementation follows the intuition we developed, using three DFS traversals to efficiently solve the problem:
Step 1: Build the Graph Representation
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
We create an adjacency list representation of the tree, where g[i]
contains all neighbors of node i
.
Step 2: Define the DFS Function
def dfs(i: int, fa: int, dist: List[int]):
for j in g[i]:
if j != fa:
dist[j] = dist[i] + 1
dfs(j, i, dist)
This recursive DFS function:
- Takes the current node
i
, its parentfa
(to avoid revisiting), and a distance arraydist
- For each neighbor
j
that isn't the parent, it updatesdist[j]
to be one more thandist[i]
- Recursively explores from neighbor
j
Step 3: Find the First Diameter Endpoint
dist1 = [-1] * n
dist1[0] = 0
dfs(0, -1, dist1)
a = dist1.index(max(dist1))
- Start DFS from node 0 (arbitrary choice)
- Find node
a
with maximum distance from node 0 - Node
a
is guaranteed to be one endpoint of the diameter
Step 4: Find the Second Diameter Endpoint and Calculate Distances from a
dist2 = [-1] * n
dist2[a] = 0
dfs(a, -1, dist2)
b = dist2.index(max(dist2))
- Start DFS from node
a
- Find node
b
with maximum distance froma
- Node
b
is the other endpoint of the diameter dist2
now contains distances from all nodes to nodea
Step 5: Calculate Distances from b
dist3 = [-1] * n dist3[b] = 0 dfs(b, -1, dist3)
- Start DFS from node
b
dist3
contains distances from all nodes to nodeb
Step 6: Determine the Answer for Each Starting Node
return [a if x > y else b for x, y in zip(dist2, dist3)]
For each node i
:
- If
dist2[i] > dist3[i]
, nodea
is farther fromi
, so returna
- Otherwise, node
b
is farther fromi
, so returnb
Time Complexity: O(n)
- We perform three DFS traversals, each taking O(n)
time.
Space Complexity: O(n)
- We store the graph adjacency list and three distance arrays, each of size n
.
The beauty of this solution lies in recognizing that the answer for any starting node must be one of only two possibilities (the diameter endpoints), allowing us to precompute everything we need with just three traversals instead of n
traversals.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider a tree with 5 nodes and edges: [[0,1], [1,2], [1,3], [3,4]]
The tree structure looks like:
0 | 1 / \ 2 3 | 4
Step 1: Build the adjacency list
g[0] = [1] g[1] = [0, 2, 3] g[2] = [1] g[3] = [1, 4] g[4] = [3]
Step 2: First DFS from node 0 Starting from node 0 with distance 0:
- Visit node 1: dist1[1] = 1
- From node 1, visit node 2: dist1[2] = 2
- From node 1, visit node 3: dist1[3] = 2
- From node 3, visit node 4: dist1[4] = 3
Result: dist1 = [0, 1, 2, 2, 3]
The farthest node is 4 with distance 3, so a = 4
(first diameter endpoint).
Step 3: Second DFS from node 4 Starting from node 4 with distance 0:
- Visit node 3: dist2[3] = 1
- From node 3, visit node 1: dist2[1] = 2
- From node 1, visit node 0: dist2[0] = 3
- From node 1, visit node 2: dist2[2] = 3
Result: dist2 = [3, 2, 3, 1, 0]
The farthest nodes are 0 and 2, both with distance 3. Let's say we pick b = 0
(second diameter endpoint).
The diameter of the tree is the path from node 4 to node 0 (length 3).
Step 4: Third DFS from node 0 Starting from node 0 with distance 0:
- Visit node 1: dist3[1] = 1
- From node 1, visit node 2: dist3[2] = 2
- From node 1, visit node 3: dist3[3] = 2
- From node 3, visit node 4: dist3[4] = 3
Result: dist3 = [0, 1, 2, 2, 3]
Step 5: Determine the answer for each starting node Now we compare distances to determine which endpoint (4 or 0) is farther from each starting node:
- Node 0: dist2[0]=3 (to node 4) vs dist3[0]=0 (to node 0) → 3 > 0, so answer is 4
- Node 1: dist2[1]=2 (to node 4) vs dist3[1]=1 (to node 0) → 2 > 1, so answer is 4
- Node 2: dist2[2]=3 (to node 4) vs dist3[2]=2 (to node 0) → 3 > 2, so answer is 4
- Node 3: dist2[3]=1 (to node 4) vs dist3[3]=2 (to node 0) → 1 < 2, so answer is 0
- Node 4: dist2[4]=0 (to node 4) vs dist3[4]=3 (to node 0) → 0 < 3, so answer is 0
Final answer: [4, 4, 4, 0, 0]
This makes intuitive sense:
- Starting from nodes 0, 1, or 2: The marking spreads toward node 4, which is the farthest endpoint
- Starting from node 3: The marking reaches node 4 quickly (distance 1) but takes longer to reach node 0 (distance 2)
- Starting from node 4: Node 0 is the farthest away and gets marked last
Solution Implementation
1class Solution:
2 def lastMarkedNodes(self, edges: List[List[int]]) -> List[int]:
3 """
4 Find the last marked node for each starting position in a tree.
5 Uses the tree diameter endpoints to determine which node is farthest.
6
7 Args:
8 edges: List of edges representing an undirected tree
9
10 Returns:
11 List where index i contains the last marked node when starting from node i
12 """
13
14 def dfs(node: int, parent: int, distances: List[int]) -> None:
15 """
16 Depth-first search to calculate distances from a starting node.
17
18 Args:
19 node: Current node being visited
20 parent: Parent node to avoid revisiting
21 distances: Array to store distances from the starting node
22 """
23 for neighbor in adjacency_list[node]:
24 if neighbor != parent:
25 distances[neighbor] = distances[node] + 1
26 dfs(neighbor, node, distances)
27
28 # Build the tree structure
29 num_nodes = len(edges) + 1
30 adjacency_list = [[] for _ in range(num_nodes)]
31
32 for u, v in edges:
33 adjacency_list[u].append(v)
34 adjacency_list[v].append(u)
35
36 # Step 1: Find one endpoint of the diameter
37 # Start DFS from node 0 to find the farthest node
38 distances_from_0 = [-1] * num_nodes
39 distances_from_0[0] = 0
40 dfs(0, -1, distances_from_0)
41
42 # Node 'endpoint_a' is the farthest from node 0
43 endpoint_a = distances_from_0.index(max(distances_from_0))
44
45 # Step 2: Find the other endpoint of the diameter
46 # Start DFS from endpoint_a to find the farthest node from it
47 distances_from_a = [-1] * num_nodes
48 distances_from_a[endpoint_a] = 0
49 dfs(endpoint_a, -1, distances_from_a)
50
51 # Node 'endpoint_b' is the farthest from endpoint_a (other end of diameter)
52 endpoint_b = distances_from_a.index(max(distances_from_a))
53
54 # Step 3: Calculate distances from endpoint_b
55 distances_from_b = [-1] * num_nodes
56 distances_from_b[endpoint_b] = 0
57 dfs(endpoint_b, -1, distances_from_b)
58
59 # Step 4: For each node, determine which endpoint is farther
60 # This gives us the last marked node when starting from each position
61 result = []
62 for dist_to_a, dist_to_b in zip(distances_from_a, distances_from_b):
63 if dist_to_a > dist_to_b:
64 result.append(endpoint_a)
65 else:
66 result.append(endpoint_b)
67
68 return result
69
1class Solution {
2 // Adjacency list to represent the tree
3 private List<Integer>[] adjacencyList;
4
5 /**
6 * Finds the last marked node for each node in a tree when marking process starts from optimal positions.
7 * The algorithm finds the diameter endpoints and determines which endpoint is farthest from each node.
8 *
9 * @param edges Array of edges representing the tree
10 * @return Array where ans[i] is the last marked node when starting from node i
11 */
12 public int[] lastMarkedNodes(int[][] edges) {
13 int nodeCount = edges.length + 1;
14
15 // Initialize adjacency list for the tree
16 adjacencyList = new List[nodeCount];
17 Arrays.setAll(adjacencyList, index -> new ArrayList<>());
18
19 // Build the undirected tree from edges
20 for (int[] edge : edges) {
21 int nodeU = edge[0];
22 int nodeV = edge[1];
23 adjacencyList[nodeU].add(nodeV);
24 adjacencyList[nodeV].add(nodeU);
25 }
26
27 // Step 1: Find one endpoint of the diameter
28 // Run DFS from node 0 to find the farthest node
29 int[] distancesFromNode0 = new int[nodeCount];
30 distancesFromNode0[0] = 0;
31 dfs(0, -1, distancesFromNode0);
32 int diameterEndpointA = maxNode(distancesFromNode0);
33
34 // Step 2: Find the other endpoint of the diameter
35 // Run DFS from the first endpoint to find the farthest node from it
36 int[] distancesFromEndpointA = new int[nodeCount];
37 distancesFromEndpointA[diameterEndpointA] = 0;
38 dfs(diameterEndpointA, -1, distancesFromEndpointA);
39 int diameterEndpointB = maxNode(distancesFromEndpointA);
40
41 // Step 3: Calculate distances from the second endpoint
42 int[] distancesFromEndpointB = new int[nodeCount];
43 distancesFromEndpointB[diameterEndpointB] = 0;
44 dfs(diameterEndpointB, -1, distancesFromEndpointB);
45
46 // Step 4: For each node, determine which diameter endpoint is farther
47 int[] result = new int[nodeCount];
48 for (int i = 0; i < nodeCount; i++) {
49 // Choose the endpoint that has greater distance to node i
50 result[i] = distancesFromEndpointA[i] > distancesFromEndpointB[i] ?
51 diameterEndpointA : diameterEndpointB;
52 }
53
54 return result;
55 }
56
57 /**
58 * Performs depth-first search to calculate distances from a starting node.
59 *
60 * @param currentNode The current node being visited
61 * @param parentNode The parent node to avoid revisiting
62 * @param distances Array to store distances from the starting node
63 */
64 private void dfs(int currentNode, int parentNode, int[] distances) {
65 // Explore all neighbors of the current node
66 for (int neighbor : adjacencyList[currentNode]) {
67 // Skip the parent node to avoid going back
68 if (neighbor != parentNode) {
69 distances[neighbor] = distances[currentNode] + 1;
70 dfs(neighbor, currentNode, distances);
71 }
72 }
73 }
74
75 /**
76 * Finds the node with maximum distance value in the given array.
77 *
78 * @param distances Array of distances
79 * @return Index of the node with maximum distance
80 */
81 private int maxNode(int[] distances) {
82 int maxIndex = 0;
83 for (int i = 0; i < distances.length; i++) {
84 if (distances[maxIndex] < distances[i]) {
85 maxIndex = i;
86 }
87 }
88 return maxIndex;
89 }
90}
91
1class Solution {
2public:
3 vector<int> lastMarkedNodes(vector<vector<int>>& edges) {
4 int n = edges.size() + 1; // Number of nodes in the tree
5
6 // Build adjacency list representation of the tree
7 adjacencyList.resize(n);
8 for (const auto& edge : edges) {
9 int u = edge[0];
10 int v = edge[1];
11 adjacencyList[u].push_back(v);
12 adjacencyList[v].push_back(u);
13 }
14
15 // First DFS: Find one endpoint of the diameter
16 // Start from node 0 and find the farthest node from it
17 vector<int> distanceFromNode0(n, 0);
18 calculateDistances(0, -1, distanceFromNode0);
19 int diameterEndpoint1 = max_element(distanceFromNode0.begin(), distanceFromNode0.end()) - distanceFromNode0.begin();
20
21 // Second DFS: Find the other endpoint of the diameter
22 // Start from diameterEndpoint1 and find the farthest node from it
23 vector<int> distanceFromEndpoint1(n, 0);
24 calculateDistances(diameterEndpoint1, -1, distanceFromEndpoint1);
25 int diameterEndpoint2 = max_element(distanceFromEndpoint1.begin(), distanceFromEndpoint1.end()) - distanceFromEndpoint1.begin();
26
27 // Third DFS: Calculate distances from the second diameter endpoint
28 vector<int> distanceFromEndpoint2(n, 0);
29 calculateDistances(diameterEndpoint2, -1, distanceFromEndpoint2);
30
31 // For each node, determine which diameter endpoint is farther
32 // This gives us the last marked node when starting from that node
33 vector<int> result;
34 for (int i = 0; i < n; ++i) {
35 if (distanceFromEndpoint1[i] > distanceFromEndpoint2[i]) {
36 result.push_back(diameterEndpoint1);
37 } else {
38 result.push_back(diameterEndpoint2);
39 }
40 }
41
42 return result;
43 }
44
45private:
46 vector<vector<int>> adjacencyList; // Graph representation using adjacency list
47
48 // DFS to calculate distances from a starting node to all other nodes
49 void calculateDistances(int currentNode, int parentNode, vector<int>& distances) {
50 // Traverse all neighbors of the current node
51 for (int neighbor : adjacencyList[currentNode]) {
52 // Skip the parent to avoid going back
53 if (neighbor != parentNode) {
54 distances[neighbor] = distances[currentNode] + 1;
55 calculateDistances(neighbor, currentNode, distances);
56 }
57 }
58 }
59};
60
1/**
2 * Finds the last marked node for each starting node in a tree
3 * when two players alternately mark nodes starting from opposite ends
4 * @param edges - Array of edges representing the tree
5 * @returns Array where ans[i] is the last marked node when starting from node i
6 */
7function lastMarkedNodes(edges: number[][]): number[] {
8 // Total number of nodes in the tree
9 const nodeCount: number = edges.length + 1;
10
11 // Build adjacency list representation of the tree
12 const adjacencyList: number[][] = Array.from({ length: nodeCount }, () => []);
13 for (const [nodeU, nodeV] of edges) {
14 adjacencyList[nodeU].push(nodeV);
15 adjacencyList[nodeV].push(nodeU);
16 }
17
18 /**
19 * Performs DFS to calculate distances from a starting node
20 * @param currentNode - Current node being visited
21 * @param parentNode - Parent of the current node (-1 if root)
22 * @param distances - Array to store distances from the starting node
23 */
24 const dfs = (currentNode: number, parentNode: number, distances: number[]): void => {
25 // Traverse all neighbors of the current node
26 for (const neighbor of adjacencyList[currentNode]) {
27 // Skip the parent node to avoid revisiting
28 if (neighbor !== parentNode) {
29 // Update distance for the neighbor
30 distances[neighbor] = distances[currentNode] + 1;
31 // Recursively visit the neighbor
32 dfs(neighbor, currentNode, distances);
33 }
34 }
35 };
36
37 // Step 1: Find distances from node 0 to all other nodes
38 const distancesFromNode0: number[] = Array(nodeCount).fill(0);
39 dfs(0, -1, distancesFromNode0);
40
41 // Find the farthest node from node 0 (this will be one end of the diameter)
42 const diameterEnd1: number = distancesFromNode0.indexOf(Math.max(...distancesFromNode0));
43
44 // Step 2: Find distances from the first diameter end to all other nodes
45 const distancesFromEnd1: number[] = Array(nodeCount).fill(0);
46 dfs(diameterEnd1, -1, distancesFromEnd1);
47
48 // Find the farthest node from diameterEnd1 (this will be the other end of the diameter)
49 const diameterEnd2: number = distancesFromEnd1.indexOf(Math.max(...distancesFromEnd1));
50
51 // Step 3: Find distances from the second diameter end to all other nodes
52 const distancesFromEnd2: number[] = Array(nodeCount).fill(0);
53 dfs(diameterEnd2, -1, distancesFromEnd2);
54
55 // Build the result array
56 const result: number[] = [];
57 for (let nodeIndex = 0; nodeIndex < nodeCount; nodeIndex++) {
58 // For each node, determine which diameter end is farther
59 // The farther end will be the last marked node in the game
60 result.push(distancesFromEnd1[nodeIndex] > distancesFromEnd2[nodeIndex] ? diameterEnd1 : diameterEnd2);
61 }
62
63 return result;
64}
65
Time and Space Complexity
Time Complexity: O(n)
The algorithm performs three depth-first searches (DFS) on the tree:
- First DFS from node 0 to find the farthest node
a
- Second DFS from node
a
to find the farthest nodeb
- Third DFS from node
b
to compute distances
Each DFS traversal visits every node exactly once and processes each edge twice (once from each direction). Since a tree with n
nodes has n-1
edges, each DFS takes O(n + 2(n-1)) = O(n)
time.
Additionally:
- Building the adjacency list
g
requires iterating through all edges:O(n-1) = O(n)
- Finding the maximum distance node using
index(max(dist))
:O(n)
- The final list comprehension with
zip
:O(n)
Total time complexity: O(n) + 3 × O(n) + O(n) + O(n) = O(n)
Space Complexity: O(n)
The space usage includes:
- Adjacency list
g
: stores all edges, requiringO(n)
space - Three distance arrays (
dist1
,dist2
,dist3
): each of sizen
, but only two exist simultaneously due to sequential execution, requiringO(n)
space - DFS recursion stack: maximum depth is
O(n)
in the worst case (skewed tree) - Result list:
O(n)
space
Total space complexity: O(n)
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Assumption About Multiple Farthest Nodes
Pitfall: A common mistake is assuming that when starting from a node, there could be multiple nodes at the maximum distance that all get marked last simultaneously. This might lead to overthinking the problem and trying to return all such nodes or handling tie-breaking unnecessarily.
Why it happens: The problem statement mentions "If there are multiple nodes that get marked at the same final time (multiple valid answers), you can return any one of them," which might mislead developers into thinking they need to track all nodes at maximum distance.
The Reality: In a tree structure, one of the key properties is that the farthest node from any given starting point will always be one of the two endpoints of the tree's diameter. While there might be multiple nodes at the same maximum distance in theory, the algorithm correctly identifies that we only need to consider the diameter endpoints.
Solution: Trust the diameter property - the algorithm already handles this correctly by only considering the two diameter endpoints as possible answers.
2. Off-by-One Error in Node Count
Pitfall: Incorrectly calculating the number of nodes in the tree.
# Wrong:
num_nodes = len(edges) # This gives n-1 nodes
# Correct:
num_nodes = len(edges) + 1 # A tree with n nodes has n-1 edges
Why it happens: It's easy to forget that a tree with n
nodes has exactly n-1
edges. Using len(edges)
directly would give you n-1
instead of n
.
Solution: Always remember the fundamental property of trees: number_of_nodes = number_of_edges + 1
3. Forgetting to Handle the Parent in DFS
Pitfall: Not tracking the parent node during DFS traversal, leading to infinite recursion.
# Wrong - will cause infinite recursion:
def dfs(node: int, distances: List[int]) -> None:
for neighbor in adjacency_list[node]:
distances[neighbor] = distances[node] + 1
dfs(neighbor, distances) # Will revisit the parent!
# Correct:
def dfs(node: int, parent: int, distances: List[int]) -> None:
for neighbor in adjacency_list[node]:
if neighbor != parent: # Skip the parent node
distances[neighbor] = distances[node] + 1
dfs(neighbor, node, distances)
Why it happens: In an undirected tree, edges are bidirectional. When traversing from node A to node B, B's adjacency list includes A, which would cause the DFS to go back to A infinitely.
Solution: Always pass and check the parent parameter in tree DFS to avoid revisiting the node you came from.
4. Using Wrong Distance Arrays for Comparison
Pitfall: Confusing which distance array corresponds to which endpoint when determining the final answer.
# Wrong - using distances from node 0 instead of endpoint distances:
return [endpoint_a if distances_from_0[i] > distances_from_b[i] else endpoint_b
for i in range(num_nodes)]
# Correct:
return [endpoint_a if distances_from_a[i] > distances_from_b[i] else endpoint_b
for i in range(num_nodes)]
Why it happens: After performing three DFS traversals, it's easy to mix up which distance array should be used. The distances_from_0
array was only used to find the first diameter endpoint and shouldn't be used in the final comparison.
Solution: Clearly name your variables and remember that you need distances from both diameter endpoints (not from the arbitrary starting node 0) to determine which endpoint is farther from each node.
5. Misunderstanding the Diameter Finding Algorithm
Pitfall: Thinking that any arbitrary farthest node from any starting point gives you a diameter endpoint.
Why it happens: While it's true that starting from any node and finding the farthest node gives you one diameter endpoint, some might think this process can be started from any previously found "farthest" node.
The Correct Process:
- Start from ANY node (we use 0) → Find farthest node → This IS a diameter endpoint
- Start from that diameter endpoint → Find farthest node → This IS the other diameter endpoint
- Do NOT continue this process further - you now have both endpoints
Solution: Understand that the two-step process (arbitrary node → endpoint A → endpoint B) is sufficient and complete for finding the tree diameter.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Want a Structured Path to Master System Design Too? Don’t Miss This!