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.

Description Hints 3 Solution Video 36:19

1245. Tree Diameter

Medium61.1% acceptance7 companiesPremium elsewhere, free here

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

Asked at 7 companies

Tiktok Salesforce

Google Meta Goldman Sachs Amazon Microsoft

Topics

Hints open one at a time

Hint 1

Start at any node A and traverse the tree to find the furthest node from it, let's call it B.

Hint 2

Having found the furthest node B, traverse the tree from B to find the furthest node from it, lets call it C.

Hint 3

The distance between B and C is the tree diameter.

36:19

Still stuck?Read the written solution, or watch a walkthrough.

Open solution