Jaspreet singh

Posted on Jul 6

Diameter of a Binary Tree

#algorithms #computerscience #java #leetcode

Problem Statement

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

The diameter is the length of the longest path between any two nodes in the tree.

Note: The path may or may not pass through the root.

Brute Force Intuition

In an interview, you can explain it like this:

For every node, calculate the height of its left subtree and right subtree. The diameter passing through that node is:

Left Height + Right Height

Take the maximum among all nodes.

The problem is that height is recomputed for every node, leading to repeated work.

Complexity

Time Complexity: O(N²)
Space Complexity: O(H)

Brute Force Code

class Solution {

    public int diameterOfBinaryTree(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        int currentDiameter =
                leftHeight + rightHeight;

        int leftDiameter =
                diameterOfBinaryTree(root.left);

        int rightDiameter =
                diameterOfBinaryTree(root.right);

        return Math.max(currentDiameter,
                Math.max(leftDiameter,
                         rightDiameter));
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        return 1 + Math.max(
                height(root.left),
                height(root.right));
    }
}

Moving Towards the Optimal Approach

Notice that while computing:

Height

we already visit every node exactly once.

Why calculate height separately?

Instead,

while returning the height,

also update the maximum diameter.

One DFS can compute both.

Pattern Recognition

Whenever you see:

Diameter
Longest Path
Height of Tree

Think:

Postorder DFS

Key Observation

For every node:

Longest Path Through Node

=

Left Height

+

Right Height

At the same time,

return:

Current Height

=

1 + max(Left Height, Right Height)

Optimal Approach

Step 1

Recursively compute:

Left Height

Step 2

Recursively compute:

Right Height

Step 3

Update:

diameter = Math.max(diameter,
                    leftHeight + rightHeight);

Step 4

Return:

1 + Math.max(leftHeight, rightHeight);

Optimal Java Solution

class Solution {

    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        height(root);

        return diameter;
    }

    private int height(TreeNode root) {

        if (root == null)
            return 0;

        int leftHeight = height(root.left);

        int rightHeight = height(root.right);

        diameter = Math.max(diameter,
                            leftHeight + rightHeight);

        return 1 + Math.max(leftHeight,
                            rightHeight);
    }
}

Dry Run

Node 4

Left = 0

Right = 0

Height = 1

Diameter = 0

Node 5

Height = 1

Node 2

Left Height = 1

Right Height = 1

Diameter = 2

Height = 2

Root 1

Left Height = 2

Right Height = 1

Diameter =

2 + 1

=

3

Final Answer:

Path:

4 → 2 → 1 → 3

Why One DFS Works?

Each recursive call already computes the height of its subtree.

While returning that height,

we can immediately compute the longest path passing through the current node.

This eliminates repeated height calculations.

Every node is visited exactly once.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N)
Space Complexity	O(H)

Where:

N = Number of Nodes
H = Height of the Tree

Interview One-Liner

Compute subtree heights using postorder DFS and update the diameter at each node as the sum of its left and right subtree heights.

Pattern Learned

Postorder DFS

↓

Left Height

↓

Right Height

↓

Update Diameter

↓

Return Height

Memory Trick