LeetCode 3787 - Find Diameter Endpoints of a Tree

The problem asks us to identify special nodes in a tree, which are nodes that serve as endpoints of any diameter path. A tree is an acyclic connected graph, and its diameter is defined as the longest simple path between any two nodes.

leetcodemediumtreebreadth-first-searchgraph-theory

LeetCode Problem 3787

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Graph Theory

Solution

Problem Understanding

The problem asks us to identify special nodes in a tree, which are nodes that serve as endpoints of any diameter path. A tree is an acyclic connected graph, and its diameter is defined as the longest simple path between any two nodes. Multiple diameter paths can exist, especially in trees with branches of equal length.

The input consists of an integer n specifying the number of nodes and an array edges containing n-1 pairs that describe the undirected edges of the tree. The output is a binary string of length n, where '1' indicates a node is special (an endpoint of at least one diameter path) and '0' otherwise.

The constraints tell us that n can be up to 10^5, meaning O(n²) approaches would be too slow. The input guarantees a valid tree, so we do not need to handle disconnected graphs or cycles.

Important edge cases include: a tree with only two nodes, a tree that is a straight line, and a tree with multiple branches of equal length leading to multiple diameter paths.

Approaches

Brute Force

A brute-force approach would be to compute the distance between every pair of nodes using BFS or DFS, find the maximum distance, and then mark the endpoints of any path that matches this maximum. This works because the diameter is the longest path, and endpoints are the nodes at the ends of these paths.

While correct, this approach is extremely inefficient for large trees because calculating all pairwise distances takes O(n²) time, which is unacceptable for n = 10^5.

Optimal Approach

The optimal approach leverages a classic property of trees: the diameter can be found with two BFS traversals. First, pick any node and perform BFS to find the farthest node u. Then, perform BFS from u to find the farthest node v. The path from u to v is one of the diameter paths.

If the tree has multiple longest paths, the endpoints can be any node that is farthest from some other node along a path of maximum length. This can be generalized by performing two BFS traversals from arbitrary nodes and marking all nodes that are at the maximum distance from either end. These nodes are guaranteed to be endpoints of some diameter path.

This method runs in O(n) time and uses O(n) space for adjacency lists and BFS queues.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n²) Compute all pairwise distances
Optimal O(n) O(n) Two BFS traversals from farthest nodes

Algorithm Walkthrough

  1. Build an adjacency list from the edges array for efficient graph traversal.
  2. Pick any node, e.g., node 0, and perform BFS to find the farthest node u. Store distances for later use.
  3. Perform BFS from node u to find the farthest node v. The path from u to v defines a diameter.
  4. Perform BFS from v to get distances from v to all other nodes.
  5. For each node i, check if it is farthest from either u or v along the diameter path. If it is, mark it as special.
  6. Convert the boolean array of special nodes to a binary string and return.

Why it works: In a tree, any diameter path is defined by two endpoints that are the farthest apart. Any node that is at the maximum distance from one of these endpoints is guaranteed to be a diameter endpoint for some path. Two BFS traversals capture all possible special nodes because any diameter endpoint is a leaf in at least one of the two BFS trees.

Python Solution

from collections import deque
from typing import List

class Solution:
    def findSpecialNodes(self, n: int, edges: List[List[int]]) -> str:
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        def bfs(start: int) -> (int, List[int]):
            dist = [-1] * n
            q = deque([start])
            dist[start] = 0
            farthest_node = start
            while q:
                node = q.popleft()
                for nei in adj[node]:
                    if dist[nei] == -1:
                        dist[nei] = dist[node] + 1
                        q.append(nei)
                        if dist[nei] > dist[farthest_node]:
                            farthest_node = nei
            return farthest_node, dist

        u, _ = bfs(0)
        v, dist_u = bfs(u)
        _, dist_v = bfs(v)

        special = ['0'] * n
        for i in range(n):
            if dist_u[i] + dist_v[i] == dist_u[v]:
                special[i] = '1'

        return ''.join(special)

The solution first constructs an adjacency list for O(1) neighbor access. The BFS helper function finds the farthest node from a starting point while storing distances. Two BFS calls identify the diameter endpoints. A final iteration marks all nodes that lie at the ends of a diameter by checking if their distances to u and v sum to the total diameter length.

Go Solution

package main

func findSpecialNodes(n int, edges [][]int) string {
    adj := make([][]int, n)
    for _, e := range edges {
        u, v := e[0], e[1]
        adj[u] = append(adj[u], v)
        adj[v] = append(adj[v], u)
    }

    bfs := func(start int) (int, []int) {
        dist := make([]int, n)
        for i := range dist {
            dist[i] = -1
        }
        queue := []int{start}
        dist[start] = 0
        farthest := start
        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]
            for _, nei := range adj[node] {
                if dist[nei] == -1 {
                    dist[nei] = dist[node] + 1
                    queue = append(queue, nei)
                    if dist[nei] > dist[farthest] {
                        farthest = nei
                    }
                }
            }
        }
        return farthest, dist
    }

    u, _ := bfs(0)
    v, distU := bfs(u)
    _, distV := bfs(v)

    special := make([]byte, n)
    for i := 0; i < n; i++ {
        if distU[i]+distV[i] == distU[v] {
            special[i] = '1'
        } else {
            special[i] = '0'
        }
    }

    return string(special)
}

The Go implementation mirrors the Python logic. It uses slices for adjacency lists and queues, and initializes distances with -1. Go requires explicit handling of slices and byte arrays for strings, but the BFS logic and final endpoint determination remain the same.

Worked Examples

Example 1

Input: n = 3, edges = [[0,1],[1,2]]

  1. BFS from node 0 → farthest node 2, distances [0,1,2]
  2. BFS from node 2 → farthest node 0, distances [2,1,0]
  3. Node distances satisfy dist_u[i]+dist_v[i] = 2 for nodes 0 and 2.
  4. Special nodes → '101'

Example 2

Input: n = 7, edges = [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]

  1. BFS from 0 → farthest node 4
  2. BFS from 4 → farthest node 6
  3. Compute distances, nodes where dist_u[i]+dist_v[i] = 4 are 0,4,5,6
  4. Special nodes → '1000111'

Example 3

Input: n = 2, edges = [[0,1]]

  1. BFS from 0 → farthest node 1
  2. BFS from 1 → farthest node 0
  3. Nodes 0 and 1 satisfy distance sum = 1
  4. Special nodes → '11'

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each BFS visits each node and edge once, two BFS traversals plus a final linear scan
Space O(n) Adjacency list, distance arrays, BFS queue, and result array

Since a tree has exactly n-1 edges, BFS traversals are linear. Memory is dominated by adjacency lists and distance arrays, which scale linearly with n.

Test Cases

# test cases
sol = Solution()

assert sol.findSpecialNodes(3, [[0,1],[1,2]]) == "101"  # straight line
assert sol.findSpecialNodes(7, [[0,1],[1,2],[2,3],[3,4],[3,5],[1,6]]) == "1000111"  # branching
assert sol.findSpecialNodes(2, [[0,1]]) == "11"  # minimum nodes
assert sol.findSpecial