Tree Diameter

Tree Diameter

What is this problem about?

The "Tree Diameter coding problem" asks for the length of the longest path between any two nodes in a tree. The length of a path is defined as the number of edges between the nodes. A tree, in this context, is an undirected graph where any two vertices are connected by exactly one path. The diameter can be found between two leaf nodes, or it might pass through the root, but it always represents the "widest" part of the tree.

Why is this asked in interviews?

This "Tree Diameter interview question" is a classic for testing a candidate's understanding of tree and graph traversals. Companies like Amazon and Microsoft use it to see if you can apply Depth-First Search (DFS) or Breadth-First Search (BFS) in a non-trivial way. It also tests your ability to think recursively—specifically, how the diameter of a tree can be calculated based on the heights of its subtrees.

Algorithmic pattern used

The "Breadth-First Search, Graph, Depth-First Search, Topological Sort, Tree interview pattern" offers two main solutions. One is a Two-BFS approach: starting from any node, find the farthest node u. Then, start a second BFS from u to find the farthest node v. The distance between u and v is the diameter. Alternatively, a Recursive DFS approach calculates the height of each node's children; the diameter passing through a node is the sum of the two largest child heights.

Example explanation

Consider a tree: 1-2, 2-3, 2-4, 4-5. Longest paths:

• 3 to 5: 3-2-4-5 (3 edges)
• 1 to 5: 1-2-4-5 (3 edges) Diameter = 3. Using Two-BFS:

1. Start at node 1. Farthest is 3, 4, or 5. Let's say we find 5.
2. Start at node 5. Farthest is 1 or 3. Distance is 3. Diameter = 3.

Common mistakes candidates make

A frequent error in the "Tree Diameter coding problem" is assuming the diameter always passes through the root. This is only true if you root the tree specifically to make it so. Another mistake is forgetting to handle trees with only one or two nodes. In the recursive approach, candidates often return the diameter instead of the height, or vice versa, which breaks the recursive logic.

Interview preparation tip

When working with the "Breadth-First Search, Graph, Depth-First Search, Topological Sort, Tree interview pattern," remember that trees are just a special type of graph. Many graph algorithms (like finding the farthest node) are simpler on trees. Practice identifying which property of a tree (like "no cycles") makes a specific optimization possible.