268. Diameter of Binary Tree

At each node, the diameter through it is left_height + right_height. Track the global maximum across all nodes.

Approach

1. DFS that returns the height of each subtree.
2. At each node, compute left_height + right_height as the path through that node.
3. Update a global maximum.
4. Return max_diameter.

Complexity

• Time: O(n)
• Space: O(h) for recursion stack

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) { this.val = val; }
    }

    private int diameter;

    public int diameterOfBinaryTree(TreeNode root) {
        diameter = 0;
        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);
        return 1 + Math.max(left, right);
    }
}