Course4all
Join us on telegram
Home/dsa/Trees/Diameter of Binary Tree

Diameter of Binary Tree

Master this topic with zero to advance depth.

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;
    }
}
← Previous QuestionSubtree of Another Tree
Next Question →Balanced Binary Tree