AlgoMaster Logo

Diameter of Binary Tree

easyFrequencyUpdated September 3, 2026

Understanding the Problem

We need to find the longest path between any two nodes in a binary tree, measured in edges (not nodes). The path does not have to pass through the root.

In Example 1, the path [4, 2, 1, 3] goes from a leaf in the left subtree, up through the root, and down to a leaf in the right subtree. It has 3 edges and is the longest in that tree. In other trees, the longest path can live entirely within one subtree and never touch the root.

Every path in a tree has a unique highest node where it bends: the path descends from that node into its left subtree and into its right subtree. Define the height of a subtree as the number of nodes on its longest downward path (0 for an empty subtree, 1 for a single leaf). The longest path bending at a given node then has height(left) + height(right) edges, because each node on the two downward chains contributes the edge connecting it to its parent.

The problem reduces to: for every node, compute height(left) + height(right), and return the maximum across all nodes.

Key Constraints:

  • Number of nodes in [1, 10^4] → An O(n^2) solution is about 10^8 operations at this size, which is borderline. O(n) is the target.
  • -100 <= Node.val <= 100 → Node values are irrelevant. Only the tree's structure matters.
  • At least 1 node → We don't need to handle the empty tree case.

Approach 1: Brute Force (DFS at Every Node)

Intuition

The diameter through any given node is height(left) + height(right), and height is a standard recursive computation. The brute force applies this directly: traverse the tree, call the height helper on both children of each node, and track the maximum sum.

The cost is redundant work. The height of a deep subtree gets recomputed once for every ancestor that asks for it.

Algorithm

  1. Write a height(node) helper that returns the number of nodes on the longest downward path from node (0 when node is null, 1 for a leaf).
  2. Traverse every node in the tree using DFS.
  3. At each node, compute height(node.left) + height(node.right), the length in edges of the longest path bending at this node.
  4. Track the maximum value seen across all nodes.
  5. Return the maximum.

Visualization and Code

Loading animation...

The next approach removes the redundancy by computing each height exactly once and tracking the diameter during the same traversal.

Approach 2: Bottom-Up DFS (Optimal)

Intuition

Approach 1 already computes heights recursively, and the diameter through a node is leftHeight + rightHeight. The two computations can share a single post-order DFS: each recursive call returns the height of its subtree, and before returning, it updates a global maximum with leftHeight + rightHeight. When the traversal finishes, the global maximum holds the answer.

In the brute force, a parent re-traverses both subtrees to learn their heights. In the post-order version, the heights arrive as return values from the two recursive calls, so each node does O(1) work beyond visiting its children once.

Algorithm

  1. Initialize a variable maxDiameter to 0.
  2. Define a helper function dfs(node) that returns the height of the subtree rooted at node, counted in nodes (0 for null, 1 for a leaf).
  3. Base case: if node is null, return 0.
  4. Recursively compute the height of the left subtree: leftHeight = dfs(node.left).
  5. Recursively compute the height of the right subtree: rightHeight = dfs(node.right).
  6. Update maxDiameter with leftHeight + rightHeight, the length in edges of the longest path bending at this node.
  7. Return 1 + max(leftHeight, rightHeight) as this subtree's height.
  8. After the DFS completes, return maxDiameter.

Visualization and Code

Loading animation...