Diameter of Binary Tree

Diameter of Binary Tree

What is this problem about?

The Diameter of Binary Tree coding problem asks you to find the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path is the number of edges between the nodes.

Why is this asked in interviews?

This is a "bread and butter" tree question at companies like Apple, Meta, and Amazon. It tests your mastery of the depth-first search interview pattern and your ability to solve a global problem by aggregating local information. It requires you to calculate two things at each node: the height of the subtree (to pass to the parent) and the diameter passing through the node (to update a global max).

Algorithmic pattern used

This problem uses Recursive DFS (Post-order Traversal).

1. Define a recursive function height(node) that returns the height of the tree rooted at node.
2. At each node, the longest path passing through it is height(left_child) + height(right_child).
3. Maintain a global variable maxDiameter and update it at every node using the sum above.
4. Return max(left_height, right_child) + 1 to the parent.

Example explanation

Tree:

    1
   / 
  2   3
 / 
4   5

1. At node 4: height=1, diameter=0.
2. At node 5: height=1, diameter=0.
3. At node 2: left_h=1, right_h=1. Diameter = $1+1=2$. Update maxDiameter = 2. Return height=2.
4. At node 3: height=1, diameter=0.
5. At node 1: left_h=2, right_h=1. Diameter = $2+1=3$. Update maxDiameter = 3. Result: 3. (Path: 4-2-1-3 or 5-2-1-3).

Common mistakes candidates make

• Double Traversal: Running a separate DFS for every node to find its height, resulting in $O(N^2)$ complexity.
• Root assumption: Thinking the longest path must go through the root.
• Edge vs Node count: Forgetting that diameter is the number of edges, which is $node\_count - 1$.

Interview preparation tip

When you need to return one value (height) but track another (diameter), always use a global variable or pass an object/array by reference. This "Bottom-up Aggregation" is a vital pattern for tree problems.