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:
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 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:
Constraints:
2 <= n <= 105edges.length == n - 1edges[i] = [ai, bi]0 <= ai, bi < nedges represents a valid tree.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.
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:
0), use BFS to find the farthest node a from that 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.b, use BFS to find the distance array dist2 from node b to all other nodes.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.
| Approach | Time | Space | When 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 DFS | O(n) | O(n) | When DFS recursion or stack traversal is already used in the system |
Practice Find Diameter Endpoints of a Tree with our built-in code editor and test cases.
Practice on FleetCode