Diameter of Binary Tree

Problem Link

Problem: Diameter of Binary Tree

Problem Statement

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.

Length = number of edges in the longest path.

Examples

Example 1

Input:

Output: 3
Explanation: Longest path = [4 → 2 → 1 → 3] or [5 → 2 → 1 → 3]

Example 2

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

Constraints

1 <= number of nodes <= 10⁴
-100 <= Node.val <= 100

Intuition

We want to find the maximum number of edges between any two nodes in the binary tree.

The longest such path will be the sum of the heights of the left and right subtrees of some node, because:

A node acts as a connector between its left and right deepest leaves.

So we do a post-order traversal (bottom-up):

Compute height of left and right subtrees
At each node, update the diameter as leftHeight + rightHeight

Approach (Recursion using Induction – Base Case – Hypothesis)

1. Base Case:

If the node is null, return height = 0.

2. Hypothesis:

Assume height(node.left) and height(node.right) give correct subtree heights.

3. Induction:

At each node:

Diameter passing through = leftHeight + rightHeight
Update global maxDiameter
Return height = 1 + max(leftHeight, rightHeight)

Code (Java)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Solution {
    private int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    private int height(TreeNode node) {
        if (node == null) return 0;

        int left = height(node.left);
        int right = height(node.right);

        diameter = Math.max(diameter, left + right); // edges = nodes - 1

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

Time and Space Complexity

Time Complexity: O(N)
Each node is visited once.
Space Complexity: O(H)
Due to recursion stack, where H is the height of the tree.

Dry Run

Input:

At node 4: height = 1, diameter = 0
At node 5: height = 1, diameter = 0
At node 2: left = 1, right = 1 → diameter = 2
At node 3: height = 1, diameter = 2
At node 1: left = 2, right = 1 → diameter = 3

Conclusion

This problem teaches you how to:

Simultaneously compute height and update other properties (diameter)
Apply post-order traversal effectively
Use a global variable to track max during recursion