How to Solve Diameter of Binary Tree on LeetCode
The Diameter of Binary Tree problem is a fundamental tree question that checks your understanding of recursion and depth tracking.
Problem Statement
Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
Example:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: The path is [4,2,1,3] or [5,2,1,3], length 3.
Why This Problem Matters for Interviews
This problem:
- Tests tree traversal and recursive depth calculations
- Forces you to optimize subtree calculations
- Is a common pattern for advanced tree problems
Approach to Diameter of Binary Tree
Recursive DFS (Optimal)
At each node, compute left/right depths and track the largest path.
Time Complexity: O(n)
Space Complexity: O(h), h = height of tree
def diameterOfBinaryTree(root) -> int:
diameter = 0
def depth(node):
nonlocal diameter
if not node:
return 0
left = depth(node.left)
right = depth(node.right)
diameter = max(diameter, left + right)
return 1 + max(left, right)
depth(root)
return diameter
Key Interview Talking Points
- Definition of diameter vs tree height
- Why the path may not go through the root
- Importance of postorder recursion
- Handling edge cases (empty, one-node tree)
Big O Complexity Recap
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive DFS | O(n) | O(h) |
Pro Interview Tips
- Draw tree and annotate depths and paths.
- Explain when diameter updates occur.
- Practice with test cases