3. Diameter of Binary Tree

Description

Diameter of Binary Tree
Given the root of a binary tree, return the length of 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 between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

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

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -100 <= Node.val <= 100

Approach - DFS

class Solution {
    int diameter = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return diameter;
    }
 
    public int dfs(TreeNode root) {
        if (root == null)
            return 0;
 
        int left = dfs(root.left);
        int right = dfs(root.right);
        diameter = Math.max(diameter, left + right);
        return 1 + Math.max(left, right);    
    }
}

Approach 1: Recursive DFS Height Calculation ($O(N)$ Time, $O(N)$ Space)

Intuition

The diameter passing through any given node is the sum of the heights of its left and right subtrees (leftHeight + rightHeight).

1. Perform a post-order traversal (Left $\to$ Right $\to$ Root) to compute the height of each subtree bottom-up.
2. At each node, calculate the path length through that node (leftHeight + rightHeight) and update a global maximum diameter variable maxDiameter.
3. Return 1 + Math.max(leftHeight, rightHeight) to pass the node’s height up to its parent.

class Solution {
    private int maxDiameter = 0;
 
    public int diameterOfBinaryTree(TreeNode root) {
        getHeight(root);
        return maxDiameter;
    }
 
    private int getHeight(TreeNode node) {
        if (node == null) return 0;
 
        int leftHeight = getHeight(node.left);
        int rightHeight = getHeight(node.right);
 
        // Update the maximum diameter found so far
        maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
 
        // Return height of current node
        return 1 + Math.max(leftHeight, rightHeight);
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Visits every node in the binary tree exactly once.
• Space Complexity: $O(N)$ worst-case call stack depth for a skewed tree ($O(\log N)$ for a balanced tree).

---

Approach 2: Iterative Postorder Traversal with Map ($O(N)$ Time, $O(N)$ Space)

Intuition

Use the standard single-stack postorder traversal template (lastVisited pointer) while maintaining a Map<TreeNode, Integer> to store the height of each processed subtree.

1. Push left children down to the leaf.
2. When popping a node from the stack (after both left and right children have been visited), retrieve depths.getOrDefault(peekNode.left, 0) and depths.getOrDefault(peekNode.right, 0).
3. Update maxDiameter with leftHeight + rightHeight and store 1 + Math.max(leftHeight, rightHeight) in the map for peekNode.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;
 
class Solution {
    public int diameterOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
 
        int maxDiameter = 0;
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, Integer> depths = new HashMap<>();
        TreeNode curr = root;
        TreeNode lastVisited = null;
 
        while (curr != null || !stack.isEmpty()) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
 
            TreeNode peekNode = stack.peek();
            // If right child exists and hasn't been processed yet, move right
            if (peekNode.right != null && lastVisited != peekNode.right) {
                curr = peekNode.right;
            } else {
                stack.pop();
                int leftHeight = depths.getOrDefault(peekNode.left, 0);
                int rightHeight = depths.getOrDefault(peekNode.right, 0);
 
                maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
                depths.put(peekNode, 1 + Math.max(leftHeight, rightHeight));
 
                lastVisited = peekNode;
            }
        }
 
        return maxDiameter;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Every node is pushed, popped, and stored in the depth map once.
• Space Complexity: $O(N)$ — Auxiliary space for the explicit stack and the height Map.

---

Easy Memory Rule

“At every node, diameter = leftHeight + rightHeight. Calculate heights bottom-up using postorder traversal and update maxDiameter!”