Skip to main content
Talentd

Find Diameter Endpoints of a Tree - Solution & Explanation

MediumPremiumFree on FleetCodeTreeBreadth-First SearchGraph13 min readAsked at: Agoda
Practice this problem

Problem Statement

You are given an undirected tree with n nodes, numbered from 0 to n - 1. It is represented by a 2D integer array edges​​​​​​​ of length n - 1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.

A node is called special if it is an endpoint of any diameter path of the tree.

Return a binary string s of length n, where s[i] = '1' if node i is special, and s[i] = '0' otherwise.

A diameter path of a tree is the longest simple path between any two nodes. A tree may have multiple diameter paths.

An endpoint of a path is the first or last node on that path.

 

Example 1:

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

Output: "101"

Explanation:

  • The diameter of this tree consists of 2 edges.
  • The only diameter path is the path from node 0 to node 2
  • The endpoints of this path are nodes 0 and 2, so they are special.

Example 2:

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

Output: "1000111"

Explanation:

The diameter of this tree consists of 4 edges. There are 4 diameter paths:

  • The path from node 0 to node 4
  • The path from node 0 to node 5
  • The path from node 6 to node 4
  • The path from node 6 to node 5

The special nodes are nodes 0, 4, 5, 6, as they are endpoints in at least one diameter path.

Example 3:

​​​​​​​

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

Output: "11"

Explanation:

  • The diameter of this tree consists of 1 edge.
  • The only diameter path is the path from node 0 to node 1
  • The endpoints of this path are nodes 0 and 1, so they are special.

 

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ai, bi]
  • 0 <= ai, bi < n
  • The input is generated such that edges represents a valid tree.

Approach Overview

Problem Overview: You are given an undirected tree with n nodes. The task is to return the two nodes that form the endpoints of the tree’s diameter. The diameter is the longest path between any two nodes in the tree.

Approach 1: BFS from Every Node (Brute Force) (Time: O(n^2), Space: O(n))

Treat the tree as an adjacency list and run a BFS starting from every node. For each start node, compute the farthest reachable node and track the maximum distance seen so far. The pair that produces the largest distance forms the diameter endpoints. This works because trees have a unique path between nodes, so BFS distance equals path length. However, running BFS n times leads to quadratic time, which becomes slow for large trees.

Approach 2: Two-Pass BFS (Tree Diameter Trick) (Time: O(n), Space: O(n))

This is the standard technique for computing tree diameter. First run BFS from any arbitrary node (commonly node 0) to find the farthest node A. Then run another BFS starting from A. The farthest node discovered in this second traversal is B, and the path A → B is the diameter. The key insight: in a tree, one endpoint of the diameter is always the farthest node from any starting point. Each traversal touches every node once, giving linear time. This approach directly uses properties of graphs and Breadth-First Search.

Approach 3: Two-Pass DFS (Time: O(n), Space: O(n))

The same idea as the BFS solution but implemented with depth-first search. Run a DFS from any node to find the farthest node A, then run another DFS from A to find the farthest node B. DFS naturally explores path depth and works well when recursion or stack-based traversal is already used in the codebase. Complexity remains linear since each edge and node is processed at most twice.

Recommended for interviews: The two-pass BFS solution. It demonstrates understanding of tree diameter properties and uses a clean linear-time traversal. Mentioning the brute-force BFS-from-every-node approach shows baseline reasoning, but recognizing the double BFS optimization signals strong graph fundamentals.

Solution

We first convert the array edges into an adjacency list representation of an undirected graph, where g[u] represents all nodes adjacent to node u.

Next, we can use Breadth-First Search (BFS) to find the diameter endpoints of the tree. The specific steps are as follows:

  1. Starting from any node (e.g., node 0), use BFS to find the farthest node a from that node.
  2. Starting from node a, use BFS again to find the farthest node b from node a, as well as the distance array dist1 from node a to all other nodes.
  3. Starting from node b, use BFS to find the distance array dist2 from node b to all other nodes.
  4. The diameter length of the tree is dist1[b]. For each node i, if dist1[i] or dist2[i] equals the diameter length, then node i is a special node.

The time complexity is O(n), and the space complexity is O(n). Where n is the number of nodes.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
BFS from Every Node (Brute Force)O(n^2)O(n)Conceptual baseline or very small trees where performance is not critical
Two-Pass BFS (Diameter Trick)O(n)O(n)Best general solution for trees using BFS traversal
Two-Pass DFSO(n)O(n)When DFS recursion or stack traversal is already used in the system

Frequently Asked Questions

Is Find Diameter Endpoints of a Tree easy or hard?
The problem is generally classified as Medium difficulty. The core challenge is recognizing the tree diameter property that allows the double BFS optimization. Once that insight is known, the implementation is straightforward graph traversal.
Find Diameter Endpoints of a Tree Python/Java solution
Most implementations build an adjacency list and run two BFS traversals. The first BFS finds the farthest node from an arbitrary start, and the second BFS finds the farthest node from that result. This pattern is identical across Python, Java, C++, Go, TypeScript, and Rust.
How to solve Find Diameter Endpoints of a Tree in O(n)?
Use the double BFS diameter technique. First perform BFS from any node to find the farthest node A. Then run BFS again starting from A to find the farthest node B. Because the input is a tree with no cycles and exactly n−1 edges, both traversals together take O(n) time.
What is the best approach for Find Diameter Endpoints of a Tree?
The most efficient approach is the two-pass BFS technique. Run a BFS from any node to find the farthest node A, then run another BFS from A to find the farthest node B. The pair (A, B) forms the diameter endpoints. This method runs in O(n) time and O(n) space for a tree with n nodes.
Is Find Diameter Endpoints of a Tree asked at Google/Amazon/Meta?
Tree diameter problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include computing the diameter length, returning the path, or identifying endpoints. Understanding the two-pass BFS or DFS technique is commonly expected in graph and tree interview rounds.
What data structure is used in Find Diameter Endpoints of a Tree?
The problem models the tree as an adjacency list graph. A queue is used for Breadth-First Search to traverse nodes level by level and compute distances. Arrays or hash maps typically track visited nodes and distances during traversal.
What is the time complexity of Find Diameter Endpoints of a Tree?
The optimal solution runs in O(n) time because each BFS traversal visits every node and edge once. Since the algorithm performs two BFS passes, the total work is still linear. Space complexity is O(n) for the adjacency list and queue used during traversal.

Ready to solve this problem?

Practice Find Diameter Endpoints of a Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Inorder Traversal

Next

Unique Binary Search Trees II