Facebook Pixel

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 and n-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:

  1. Tree Traversal: We need to traverse the tree to find distances between nodes, which DFS handles efficiently.

  2. 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
  3. 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.

  4. 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Find both endpoints of the diameter (let's call them a and b)
  2. For each starting node i, determine which endpoint (a or b) 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 parent fa (to avoid revisiting), and a distance array dist
  • For each neighbor j that isn't the parent, it updates dist[j] to be one more than dist[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 from a
  • Node b is the other endpoint of the diameter
  • dist2 now contains distances from all nodes to node a

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 node b

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], node a is farther from i, so return a
  • Otherwise, node b is farther from i, so return b

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 Evaluator

Example 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 node b
  • 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, requiring O(n) space
  • Three distance arrays (dist1, dist2, dist3): each of size n, but only two exist simultaneously due to sequential execution, requiring O(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:

  1. Start from ANY node (we use 0) → Find farthest node → This IS a diameter endpoint
  2. Start from that diameter endpoint → Find farthest node → This IS the other diameter endpoint
  3. 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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More