EasyNeetCode150TreeDepth-First SearchBinary Tree
Diameter of Binary Tree
Find longest path between any two nodes.
Examples
Input
root = [1,2,3,4,5]
Output
3
Path: 4->2->1->3 or 5->2->1->3.
Constraints
- •
Number of nodes in [1,10^4] - •
-100 <= Node.val <= 100
Approaches
For each node, find longest path through it.
CodeT: O(n^2) | S: O(h) stack
Track depth, update diameter.
CodeT: O(n) | S: O(h) stack
def diameterOfBinaryTree(root):
self.mx=0
def d(n):
if not n: return 0
l=d(n.left); r=d(n.right)
self.mx=max(self.mx,l+r)
return 1+max(l,r)
d(root); return self.mxSame approach.
CodeT: O(n) | S: O(h)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2) | O(h) stack | For each node, find longest path through it. |
| DFS | O(n) | O(h) stack | Track depth, update diameter. |
| DFS Single Pass | O(n) | O(h) | Same approach. |
Brute Force
T: O(n^2)S: O(h) stack
For each node, find longest path through it.
DFS
T: O(n)S: O(h) stack
Track depth, update diameter.
DFS Single Pass
T: O(n)S: O(h)
Same approach.
Common Mistakes
Not updating diameter at each node
Using diameter as depth
Not handling single node