The Diameter of a Binary Tree is one of those interview questions that looks complicated at first, but becomes surprisingly elegant once you understand what you're actually calculating.

In this article, we'll build the intuition behind the solution before looking at the code.

The Problem

We're given the root of a binary tree.

The diameter is defined as the longest path between any two nodes in the tree.

A few important details:

  • The path does not have to pass through the root.
  • The length of a path is measured by the number of edges, not nodes.
  • A node cannot appear twice in the same path.

For example:

        1
         \
          2
         / \
        3   4
       /
      5

The longest path is:

5 → 3 → 2 → 4

which contains 3 edges, so the answer is:

3

The First Intuition

When people first see this problem, they often think:

"Should I try every possible pair of nodes?"

That would work, but it would be extremely inefficient.

Instead, notice something interesting.

For every node, we can ask:

"If this node were the highest point of the path, how long would that path be?"

Consider this node:

      X
     / \
    L   R

The longest path passing through X would simply be:

height(left subtree) + height(right subtree)

Why?

Because the path goes:

deepest node on the left
        ↑
        X
        ↓
deepest node on the right

So if we knew the height of every subtree, we could compute the longest path through every node.

Why DFS?

A node's height depends on the heights of its children.

That means we must compute the children first.

This is exactly what post-order DFS does.

Left
↓

Right
↓

Current Node

By the time we process the current node, both subtree heights are already known.

What Does DFS Return?

This is the key insight.

Our DFS doesn't return the diameter.

Instead, it returns the height of the subtree.

Height =
1 + max(left height, right height)

For example,

      A
     /
    B
   /
  C
height(C) = 1
height(B) = 2
height(A) = 3

Notice that we're counting nodes, not edges.

That's perfectly fine because when we compute

left height + right height

the math naturally gives us the number of edges in the longest path through that node.

Updating the Diameter

At every node we already know

  • left subtree height
  • right subtree height

So the longest path through this node is simply

left + right

We compare it with the best answer we've seen so far.

diameter = max(diameter, left + right)

This happens for every node in the tree.

Even if the actual diameter doesn't pass through the root, we'll eventually visit the node where it does pass through.

Walking Through an Example

Consider:

        1
       / \
      2   3
     / \
    4   5

Step 1

Leaf nodes:

4
5
3

Each has height:

1

Current diameter:

0

Step 2

Process node 2

left = 1
right = 1

Diameter through node 2:

1 + 1 = 2

Update answer:

diameter = 2

Height returned:

1 + max(1,1)
=
2

Step 3

Process root

left = 2
right = 1

Diameter through root:

2 + 1 = 3

Update:

diameter = 3

Height returned:

3

Final answer:

3

The Code

from typing import Optional

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        self.res = 0

        def dfs(curr):
            if not curr:
                return 0

            left = dfs(curr.left)
            right = dfs(curr.right)

            # Longest path passing through this node
            self.res = max(self.res, left + right)

            # Return height of this subtree
            return 1 + max(left, right)

        dfs(root)
        return self.res

Why This Works

Every node contributes two pieces of information:

  1. The height of its subtree (returned to its parent).
  2. The longest path passing through itself (used to update the global diameter).

Since every node is visited exactly once, we never perform unnecessary work.

Complexity

Time Complexity

O(n)

Every node is visited exactly once.

Space Complexity

O(h)

where h is the height of the tree.

  • Best case (balanced tree):
O(log n)
  • Worst case (completely skewed tree):
O(n)

because of the recursion stack.

Interview Takeaways

If this question comes up in an interview, the interviewer is usually looking for these key insights:

  • Recognise that the diameter at a node is left_height + right_height.
  • Use post-order DFS so child heights are available before processing the parent.
  • Return the height from the recursive function, not the diameter.
  • Keep a global variable (or non-local variable) to track the maximum diameter seen so far.

Once you understand that the DFS is responsible only for returning subtree heights, the entire solution becomes a clean one-pass traversal of the tree.