Problem
Given the root of a binary tree, return the length of its diameter.The diameter of a binary tree is the length of the longest path between any two nodes. This path may or may not pass through the root. The length of the path is measured by the number of edges between the two nodes.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [1,2,3,4,5]
1
/ \
2 3
/ \
4 5
Output
3 Solution
This solution uses Depth-First Search (DFS) with recursion. For every node, we calculate the maximum depth of its left and right subtrees.The longest path passing through the current node is the sum of the left and right subtree depths. This value represents the number of edges between the deepest nodes on both sides.
While calculating the depth of each subtree, we continuously update the maximum diameter found so far. The recursive method returns the height of the current subtree to its parent.
private int diameter = 0;
public int diameterOfBinaryTree(TreeNode root) {
depth(root);
return diameter;
}
private int depth(TreeNode node) {
if (node == null) {
return 0;
}
int leftDepth = depth(node.left);
int rightDepth = depth(node.right);
// Update the longest path through this node.
diameter = Math.max(diameter, leftDepth + rightDepth);
return 1 + Math.max(leftDepth, rightDepth);
}
Complexity
Each node in the binary tree is visited exactly once, resulting in a time complexity ofO(n).
The recursive call stack can grow up to the height of the tree, resulting in an extra space complexity of
O(h), where h is the height of the tree.