Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Subtree of Another Tree
Bookmark
DFS + Same Tree
Serialization
Merkle Hash
Input
Example 1 (true)
Example 2 (false)
Match Mid-Tree (true)
Custom
tree
=
[3, 4, 5, 1, 2]
,
subTree
=
[4, 1, 2]
root
subRoot
3
4
5
1
2
4
1
2
stack
does
root
contain a copy of
subRoot
?
root
subRoot
3
4
5
1
2
4
1
2
stack
does
root
contain a copy of
subRoot
?
root
subRoot
3
4
5
1
2
4
1
2
stack
3
top
stack = [
3
]
root
subRoot
3
4
5
1
2
4
1
2
stack
3 ≠ 4
: values differ
root
subRoot
3
4
5
1
2
4
1
2
stack
candidate
3
rejected, keep searching
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
push
5
(right child)
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
candidate
4
: run isSameTree
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
4 = 4
, compare children
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
1 = 1
, compare children
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
subRoot matches at 4
root
subRoot
3
4
5
1
2
4
1
2
stack
5
top
return true
algo
master
.
io
Step:
Start: does root contain a subtree identical to subRoot?
0 / 12
Input
Example 1 (true)
Example 2 (false)
Match Mid-Tree (true)
Custom
tree
=
[3, 4, 5, 1, 2]
,
subTree
=
[4, 1, 2]
0 / 12
algo
master
.
io
Step:
Start: does root contain a subtree identical to subRoot?
