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
call stack
does
root
contain a copy of
subRoot
?
root
subRoot
3
4
5
1
2
4
1
2
call stack
does
root
contain a copy of
subRoot
?
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
top
3 ≠ 4
: values differ
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
top
not identical at
3
, recurse into the left subtree
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
4
top
4 = 4
, compare children
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
4
top
1 = 1
, compare children
root
subRoot
3
4
5
1
2
4
1
2
∅
∅
call stack
3
4
top
∅ = ∅
, identical here
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
4
top
2 = 2
, compare children
root
subRoot
3
4
5
1
2
4
1
2
∅
∅
call stack
3
4
top
∅ = ∅
, identical here
root
subRoot
3
4
5
1
2
4
1
2
call stack
3
4
top
subRoot matches at 4
: return true
root
subRoot
3
4
5
1
2
4
1
2
call stack
return true
algo
master
.
io
Step:
Start: visit every node of root and check whether the tree rooted there is identical to subRoot
0 / 14
Input
Example 1 (true)
Example 2 (false)
Match Mid-Tree (true)
Custom
tree
=
[3, 4, 5, 1, 2]
,
subTree
=
[4, 1, 2]
0 / 14
algo
master
.
io
Step:
Start: visit every node of root and check whether the tree rooted there is identical to subRoot
