Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Diameter of Binary Tree
Bookmark
Brute Force
Bottom-Up DFS
Input
Example 1
Example 2
Longer Path
Custom
tree
=
[1, 2, 3, 4, 5]
1
2
3
4
5
scans
0
diameter
0
brute force: re-scan both subtrees at every node
1
2
3
4
5
scans
0
diameter
0
brute force: re-scan both subtrees at every node
1
2
3
4
5
scans
3
diameter
0
height(left) =
2
, scanned 3 nodes
1
2
3
4
5
scans
4
diameter
3
maxDiameter =
3
1
2
3
4
5
scans
6
diameter
3
height(right) =
1
, scanned 1 node
1
2
3
4
5
scans
6
diameter
3
measure the path through
4
1
2
3
4
5
scans
6
diameter
3
path through
4
:
0
+
0
=
0
edges
1
2
3
4
5
scans
6
diameter
3
height(left) =
0
, scanned 0 nodes
1
2
3
4
5
scans
6
diameter
3
0 does not beat
3
1
2
3
4
5
scans
6
diameter
3
height(right) =
0
, scanned 0 nodes
1
2
3
4
5
scans
6
diameter
3
return 3
algo
master
.
io
Step:
Start: the diameter is the longest path between any two nodes
0 / 27
Input
Example 1
Example 2
Longer Path
Custom
tree
=
[1, 2, 3, 4, 5]
0 / 27
algo
master
.
io
Step:
Start: the diameter is the longest path between any two nodes
