Tree Diameter - Solution & Explanation

Q: Is Tree Diameter easy or hard?

Tree Diameter is generally considered a medium-level problem. The implementation of DFS is simple, but recognizing the two-pass traversal property of trees requires some graph algorithm intuition.

Q: Tree Diameter Python/Java solution

Most implementations build an adjacency list using a dictionary or list of lists, then run two DFS traversals. The same logic works across Python, Java, C++, Go, and TypeScript with only minor syntax differences.

Q: How to solve Tree Diameter in O(n)?

Convert the edge list into an adjacency list. Perform a DFS from any node to locate the farthest node A. Then perform a second DFS starting from A to find the farthest node B and measure the distance. That distance equals the tree diameter.

Q: What is the best approach for Tree Diameter?

The most efficient method is the Two DFS Passes technique. Run a DFS from any node to find the farthest node A, then run another DFS from A to find the farthest node B. The distance between A and B is the diameter. This approach runs in O(n) time and O(n) space.

Q: Is Tree Diameter asked at Google/Amazon/Meta?

Tree diameter is a common graph and tree interview problem and variations appear at companies like Google, Amazon, Meta, and Microsoft. It tests graph traversal skills, adjacency list construction, and understanding of tree properties.

Q: What data structure is used in Tree Diameter?

The tree is typically stored as an adjacency list because the input is given as edges. Traversal uses either Depth-First Search (DFS) with recursion or Breadth-First Search (BFS) with a queue to compute distances between nodes.

Q: What is the time complexity of Tree Diameter?

The optimal algorithm runs in O(n) time where n is the number of nodes in the tree. Each DFS or BFS traversal visits every node and edge once, and the algorithm performs exactly two traversals.

MediumPremiumFree on FleetCodeTree Depth-First Search Breadth-First Search Graph7 min readAsked at: Amazon, Microsoft, Goldman Sachs +4

Practice this problem

Problem Statement

The diameter of a tree is the number of edges in the longest path in that tree.

There is an undirected tree of n nodes labeled from 0 to n - 1. You are given a 2D array edges where edges.length == n - 1 and edges[i] = [a_i, b_i] indicates that there is an undirected edge between nodes a_i and b_i in the tree.

Return the diameter of the tree.

Example 1:

Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: The longest path of the tree is the path 1 - 0 - 2.

Example 2:

Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: The longest path of the tree is the path 3 - 2 - 1 - 4 - 5.

Constraints:

n == edges.length + 1
1 <= n <= 10⁴
0 <= a_i, b_i < n
a_i != b_i

Approach Overview

Problem Overview: You are given an undirected tree represented as a list of edges. The goal is to compute the tree’s diameter — the length of the longest path between any two nodes. The path does not need to pass through the root because the tree is unrooted.

Approach 1: DFS/BFS from Every Node (O(n^2) time, O(n) space)

Build an adjacency list for the tree, then run a traversal from every node. Each traversal (using DFS or BFS) computes the farthest distance reachable from that starting node. Track the maximum distance found across all traversals. Because a tree with n nodes has n-1 edges, each traversal costs O(n), and repeating it for all nodes results in O(n^2) time with O(n) space for the adjacency list and visited set. This method is straightforward but inefficient for large trees.

Approach 2: Two DFS Passes (O(n) time, O(n) space)

The key property of trees: if you start from any node and find the farthest node from it, that node must be one endpoint of the diameter. Run a first DFS from an arbitrary node (often node 0) to find the farthest node A. Then run a second DFS starting from A to find the farthest node B. The distance between A and B is the tree diameter. Each traversal processes every node and edge exactly once, giving O(n) time and O(n) space for the adjacency list and recursion stack. This technique works because trees have exactly one simple path between any two nodes.

Both traversals operate on a graph representation of the tree, so you first convert the edge list into an adjacency list. Either Depth-First Search or Breadth-First Search works for finding the farthest node. The underlying structure is still a tree, but treating it as an undirected graph simplifies traversal.

Recommended for interviews: The Two DFS Passes approach is the expected solution. Interviewers want to see that you recognize the diameter property and reduce the search from O(n^2) to O(n). Mentioning the brute force traversal first shows understanding of the problem space, then moving to the two-pass DFS demonstrates algorithmic optimization.

Solution

First, we arbitrarily select a node and start a depth-first search (DFS) from this node to find the farthest node from it, denoted as node a. Then, we start another DFS from node a to find the farthest node from node a, denoted as node b. It can be proven that the path between node a and node b is the diameter of the tree.

Time complexity is O(n), and space complexity is O(n), where n is the number of nodes.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
DFS/BFS from Every Node	O(n^2)	O(n)	Useful for understanding the diameter definition or when constraints are very small
Two DFS Passes (Optimal)	O(n)	O(n)	Standard optimal solution for tree diameter problems in interviews and production code
Two BFS Passes	O(n)	O(n)	Alternative to DFS when recursion depth is a concern or iterative traversal is preferred

Video Solution

Diameter Of Undirected Graph | Tree Diameter | Leetcode 1245 | Graph Concepts & Qns - 44 | MIK • codestorywithMIK • 13,187 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Tree Diameter easy or hard?

Tree Diameter is generally considered a medium-level problem. The implementation of DFS is simple, but recognizing the two-pass traversal property of trees requires some graph algorithm intuition.

Tree Diameter Python/Java solution

Most implementations build an adjacency list using a dictionary or list of lists, then run two DFS traversals. The same logic works across Python, Java, C++, Go, and TypeScript with only minor syntax differences.

How to solve Tree Diameter in O(n)?

Convert the edge list into an adjacency list. Perform a DFS from any node to locate the farthest node A. Then perform a second DFS starting from A to find the farthest node B and measure the distance. That distance equals the tree diameter.

What is the best approach for Tree Diameter?

The most efficient method is the Two DFS Passes technique. Run a DFS from any node to find the farthest node A, then run another DFS from A to find the farthest node B. The distance between A and B is the diameter. This approach runs in O(n) time and O(n) space.

Is Tree Diameter asked at Google/Amazon/Meta?

Tree diameter is a common graph and tree interview problem and variations appear at companies like Google, Amazon, Meta, and Microsoft. It tests graph traversal skills, adjacency list construction, and understanding of tree properties.

What data structure is used in Tree Diameter?

The tree is typically stored as an adjacency list because the input is given as edges. Traversal uses either Depth-First Search (DFS) with recursion or Breadth-First Search (BFS) with a queue to compute distances between nodes.

What is the time complexity of Tree Diameter?

The optimal algorithm runs in O(n) time where n is the number of nodes in the tree. Each DFS or BFS traversal visits every node and edge once, and the algorithm performs exactly two traversals.

Ready to solve this problem?

Practice Tree Diameter with our built-in code editor and test cases.

Practice on FleetCode

Count Subtrees With Max Distance Between Cities

Find Minimum Diameter After Merging Two Trees

Problem Info

DifficultyMedium

Acceptance61.1%

Approaches1

Reading time7 min

Asked at

Amazon Microsoft Goldman Sachs Meta Salesforce