Diameter of Binary Tree
Problem
Given the root of a binary tree, return the length (number of edges) of the longest path between any two nodes in the tree. The path may or may not pass through the root.
Examples
Example 1
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The longest path is 4 -> 2 -> 1 -> 3 (or 5 -> 2 -> 1 -> 3), 3 edges.
Constraints
- •
The number of nodes is in the range [1, 10^4]
Hints
Hint 1
The diameter through any single node equals the sum of its left and right subtree HEIGHTS — but the overall answer might come from a node that isn't the root.
Hint 2
You need to compute height anyway (recursively) — the trick is updating a running 'best diameter seen so far' as a side effect of that same height computation, rather than a separate pass.
Hint 3
Don't recompute height from scratch at every node (that's O(n^2)) — compute it bottom-up once, and the diameter check piggybacks on the same traversal.
Solutions
public int diameterOfBinaryTreeBruteForce(TreeNode root) {
if (root == null) return 0;
int throughRoot = height(root.left) + height(root.right);
int bestInLeft = diameterOfBinaryTreeBruteForce(root.left);
int bestInRight = diameterOfBinaryTreeBruteForce(root.right);
return Math.max(throughRoot, Math.max(bestInLeft, bestInRight));
}
private int height(TreeNode node) {
if (node == null) return 0;
return 1 + Math.max(height(node.left), height(node.right));
}Time: O(n^2) worst case · Space: O(h)