Diameter of Binary Tree

Easytreedepth-first-searchrecursion
Category: Trees
Companies that ask this question:
AmazonFacebookGoogleMicrosoft
LeetCode →NeetCode →

Approach

Diameter of Binary Tree

Problem Statement

Given the root of a binary tree, return the diameter of the tree.

The diameter of a binary tree is 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 represented by the number of edges between nodes.

Examples

Example 1

Input: root = [1,2,3,4,5]
Output: 3

Tree:
      1
     / \
    2   3
   / \
  4   5

Longest path: [4,2,1,3] with 3 edges

Example 2

Input: root = [1,2]
Output: 1

Tree:
    1
   /
  2

Longest path: [2,1] with 1 edge

Intuition

The diameter at any node = left_height + right_height (edges on both sides).

Key insight: The longest path through a node is the sum of:

  • Maximum depth of left subtree
  • Maximum depth of right subtree

We need to check this for every node, not just the root!

Pattern Recognition

This is a Tree DFS + Global Variable problem with:

  • Post-order traversal (calculate children before parent)
  • Track global maximum while computing heights
  • Similar to Max Depth but with extra bookkeeping

Approach

  1. Global Variable: Track maximum diameter seen so far
  2. DFS Function: Returns height of subtree
  3. At Each Node:
    • Calculate left subtree height
    • Calculate right subtree height
    • Update global max diameter = max(current_max, left_height + right_height)
    • Return 1 + max(left_height, right_height) to parent

Why this works:

  • Every node is considered as a potential "bridge" in the longest path
  • The diameter through a node = heights of both subtrees
  • We check all possible paths by visiting all nodes

Key Difference from Max Depth

  • Max Depth: Return height only
  • Diameter: Return height BUT also track left_height + right_height as diameter candidate

Edge Cases

  • Single node → diameter = 0 (no edges)
  • Null tree → diameter = 0
  • Skewed tree → diameter = height - 1
  • Longest path doesn't go through root

Complexity Analysis

  • Time: O(n) where n = number of nodes

    • Visit each node once
    • O(1) work per node

  • Space: O(h) where h = height

    • Recursion call stack
    • O(log n) for balanced, O(n) for skewed

Solution

java
1class TreeNode {
2    int val;
3    TreeNode left;
4    TreeNode right;
5    TreeNode() {}
6    TreeNode(int val) { this.val = val; }
7    TreeNode(int val, TreeNode left, TreeNode right) {
8        this.val = val;
9        this.left = left;
10        this.right = right;
11    }
12}
13
14class Solution {
15    private int diameter = 0;
16
17    public int diameterOfBinaryTree(TreeNode root) {
18        height(root);
19        return diameter;
20    }
21
22    private int height(TreeNode node) {
23        // Base case: null node has height 0
24        if (node == null) {
25            return 0;
26        }
27
28        // Calculate height of left and right subtrees
29        int leftHeight = height(node.left);
30        int rightHeight = height(node.right);
31
32        // Update global diameter (path through this node)
33        diameter = Math.max(diameter, leftHeight + rightHeight);
34
35        // Return height of this subtree
36        return 1 + Math.max(leftHeight, rightHeight);
37    }
38}
39
Loading visualizer...