Back to Trees
Easy
Diameter of Binary Tree
Given the `root` of a binary tree, return the length of the diameter of the 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. The length of a path between two nodes is represented by the number of edges between them.
Examples
Input:root = [1,2,3,4,5]
Output:3
3 is the length of the path [4,2,1,3] or [5,2,1,3].
Input:root = [1,2]
Output:1
Constraints
The number of nodes in the tree is in the range [1, 10^4].-100 <= Node.val <= 100
Approach
For every node, calculate the maximum depth of its left and right subtrees. The diameter passing through that node is `leftDepth + rightDepth`. We can do this recursively for all nodes and keep track of the maximum diameter found. However, this recalculates depths multiple times.
Complexity Analysis
Time Complexity
O(n^2)
Space Complexity
O(h)
This approach is inefficient because it recalculates the depths of nodes multiple times.
Solution.java
class Solution { public int diameterOfBinaryTree(TreeNode root) { if (root == null) return 0; int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); int currentDiameter = leftDepth + rightDepth; int leftDiameter = diameterOfBinaryTree(root.left); int rightDiameter = diameterOfBinaryTree(root.right); return Math.max(currentDiameter, Math.max(leftDiameter, rightDiameter)); } private int maxDepth(TreeNode root) { if (root == null) return 0; return 1 + Math.max(maxDepth(root.left), maxDepth(root.right)); }}