Diameter of Binary Tree
The key idea
The longest path that bends at a given node equals the depth of its left subtree plus the depth of its right subtree, counted in edges. Run one post-order DFS that returns each node's depth and, at every node, update a running
best with left + right. The diameter is the largest such sum, because the true longest path bends at exactly one node.Problem
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 the 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.
Constraints
- The number of nodes in the tree is in the range
[1, 10^4]. -100 <= Node.val <= 100
Examples
Input: root = [1,2,3,4,5]
Output: 3
Input: root = [1,2]
Output: 1
Complexity
Time: O(n) Space: O(h)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Tree / Recursion problems
- Balanced Binary TreeEASY
- Binary Tree CamerasHARD
- Binary Tree Inorder TraversalEASY
- Binary Tree Maximum Path SumHARD
- Binary Tree PathsEASY
- Binary Tree Postorder TraversalEASY
- Binary Tree Preorder TraversalEASY
- House Robber IIIMEDIUM
- Construct Binary Tree from Inorder and Postorder TraversalMEDIUM
- Construct Binary Tree from Preorder and Inorder TraversalMEDIUM
- Convert BST to Greater TreeMEDIUM
- Count Complete Tree NodesEASY