Course4all

Diameter of Binary Tree

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Trees.

Diameter of Binary Tree

Find the length of the longest path between any two nodes in a tree.
Easy

Examples

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

Level I: Recursive DFS (Bottom-Up)

Intuition

The diameter of a tree at node NN is the maximum of:
  1. Depth of Left Subtree + Depth of Right Subtree.
  2. Diameter of Left Subtree.
  3. Diameter of Right Subtree. Using a bottom-up approach, we can calculate height and track the max diameter simultaneously.
⏱ O(N)💾 O(H)

Detailed Dry Run

Node(2): Left height=1, Right height=1. Diameter = 2. Max = 2. Return height=2.
java
class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return max;
    }
    private int height(TreeNode node) {
        if (node == null) return 0;
        int l = height(node.left), r = height(node.right);
        max = Math.max(max, l + r);
        return 1 + Math.max(l, r);
    }
}
Approach 2

Level II: Recursive Bottom-Up (Pair Result)

Intuition

Instead of using a global variable, each recursive call returns a pair: (height, diameter_so_far). This is a cleaner functional approach.

Diagram

Node(2) returns {Height: 2, Diameter: 2} Node(3) returns {Height: 1, Diameter: 0} Root(1) calc: max(2.H+3.H, 2.D, 3.D) -> max(3, 2, 0) = 3.
⏱ O(N)💾 O(H)

Detailed Dry Run

DFS returns {h, d}. For null: {0, 0}. For leaf: {1, 0}. For 2: l={1,0}, r={1,0} -> {2, 2}. Final root returns {max_h, max_d}.
java
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        return dfs(root)[1];
    }
    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] l = dfs(node.left), r = dfs(node.right);
        int h = 1 + Math.max(l[0], r[0]);
        int d = Math.max(l[1], Math.max(r[1], l[0] + r[0]));
        return new int[]{h, d};
    }
}
Approach 3

Level III: Optimal (Iterative Post-order)

Intuition

We can solve this iteratively by performing a Post-order traversal using a stack. We keep a Map to store the heights of nodes as we finish processing them. For each node, diameter = height(left) + height(right).

Logic

  1. Use a stack for post-order.
  2. Store computed heights in Map<TreeNode, Integer>.
  3. height = 1 + max(h_left, h_right).
  4. diameter = h_left + h_right.
⏱ O(N)💾 O(N)

Detailed Dry Run

Stack processes leaves first, populating Map(leaf) = 1. Then Parent(2) sees l=1, r=1, Map(2)=2, MaxD=2. Root(1) sees Map(2)=2, Map(3)=1, MaxD=max(2, 3)=3.
java
public class Main {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxD = 0;
        Map<TreeNode, Integer> map = new HashMap<>();
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root, last = null;
        while (curr != null || !stack.isEmpty()) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                TreeNode peek = stack.peek();
                if (peek.right != null && last != peek.right) {
                    curr = peek.right;
                } else {
                    TreeNode node = stack.pop();
                    int l = map.getOrDefault(node.left, 0);
                    int r = map.getOrDefault(node.right, 0);
                    maxD = Math.max(maxD, l + r);
                    map.put(node, 1 + Math.max(l, r));
                    last = node;
                }
            }
        }
        return maxD;
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionSubtree of Another Tree
Next Question →Balanced Binary Tree