Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Longest Univalue Path
Bookmark
Brute Force
Single DFS
Input
Example 1
Example 2
All Same
Custom
tree
=
[5, 4, 5, 1, 1, null, 5]
5
4
5
1
1
5
visits = 0
max = 0
longest path of
equal values
(counted in edges)
5
4
5
1
1
5
visits = 0
max = 0
longest path of
equal values
(counted in edges)
5
4
5
1
1
5
visits = 2
max = 0
value differs from
5
, this branch adds 0
5
4
5
1
1
5
visits = 4
max = 0
the run so far returns upward
5
through=2
4
5
1
1
5
visits = 5
max = 2
probe the left subtree for a run of
4
5
through=2
4
through=0
5
1
1
5
visits = 7
max = 2
move the anchor into the
left
subtree
5
through=2
4
through=0
5
1
through=0
1
5
visits = 8
max = 2
through 1: 0 + 0 = 0
, best stays 2
5
through=2
4
through=0
5
1
through=0
1
through=0
5
visits = 9
max = 2
through 1: 0 + 0 = 0
, best stays 2
5
through=2
4
through=0
5
1
through=0
1
through=0
5
visits = 10
max = 2
probe the right subtree for a run of
5
5
through=2
4
through=0
5
through=1
1
through=0
1
through=0
5
visits = 12
max = 2
anchor
5
, measure a fresh run down each side
5
4
5
1
1
5
visits = 12
max = 2
return 2
algo
master
.
io
Step:
Start: find the longest path where every node shares one value
0 / 40
Input
Example 1
Example 2
All Same
Custom
tree
=
[5, 4, 5, 1, 1, null, 5]
0 / 40
algo
master
.
io
Step:
Start: find the longest path where every node shares one value
