What is Tree Diameter?
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.
Visual Example
The longest path is [4, 2, 1, 5] (or [5, 2, 1, 4]) which has a length of 3 edges.
Algorithm Strategy
1. Compute Subtree Heights
At any given node, recursively calculate the height of its left subtree and its right subtree. A null node has a height of 0.
2. Update Max Diameter
The longest path passing through the current node is `leftHeight + rightHeight`. Keep track of the maximum sum seen so far globally.
3. Return Height
Return `Math.max(leftHeight, rightHeight) + 1` to the parent node so it can compute its own height and local diameter.
Complexity Analysis
Where N is the number of nodes, and H is the height of the tree (recursion stack).
Time Complexity: O(N)
Key Takeaways
- You calculate the answer (diameter) as a side effect while performing a standard depth-first height calculation.
- The diameter does not strictly have to pass through the absolute root of the entire tree. It can be localized to a left or right subtree.