Diameter of Binary 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.
Constraints:
- The number of nodes in the tree is in the range [1, 10^4].
- 1 <= Node.val <= 10^5
Examples:
Input: [1,2,3,4,5]
Output: 3
Explanation: The diameter is the path [4,2,1,3] or [5,2,1,3].
Solutions
Depth-First Search
Time: O(N)Space: O(H)
We use a depth-first search to calculate the height of each subtree and update the maximum diameter found so far.
var diameterOfBinaryTree = function (root) {
let maxDiameter = 0;
function dfs(node) {
if (!node) return 0;
const leftHeight = dfs(node.left);
const rightHeight = dfs(node.right);
maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
return Math.max(leftHeight, rightHeight) + 1;
}
dfs(root);
return maxDiameter;
};
Follow-up:
What if the tree is not binary?
