Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Delete Nodes And Return Forest
Bookmark
BFS Parent Tracking
Post-Order DFS
Input
Example 1
Example 2
Example 3
Custom
tree
=
[1, 2, 3, 4, 5, 6, 7]
,
toDelete
=
[3, 5]
delete
3
5
1
2
3
4
5
6
7
parents
queue
forest
pass 1 records every parent, pass 2 deletes and promotes children
delete
3
5
1
2
3
4
5
6
7
parents
queue
forest
pass 1 records every parent, pass 2 deletes and promotes children
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
queue
2
3
front
pass 1: parents
forest
parentMap[
3
] =
1
, enqueue right child
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
4→2
5→2
queue
4
5
front
pass 1: parents
forest
pass 1: dequeue
3
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
7
front
pass 1: parents
forest
pass 1: dequeue
6
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
2
3
front
pass 2: delete
forest
enqueue right child
3
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
3
4
5
front
pass 2: delete
forest
enqueue right child
5
delete
3
5
1
2
3
4
5
6
7
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
4
5
6
7
front
pass 2: delete
forest
3
is in deleteSet: disconnect it, promote its children
delete
3
5
1
2
3
4
5
6
7
root
root
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
5
6
7
front
pass 2: delete
forest
6
7
4
is not in deleteSet, nothing to do
delete
3
5
1
2
3
4
5
6
7
root
root
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
7
front
pass 2: delete
forest
6
7
pass 2: dequeue
6
delete
3
5
1
2
3
4
5
6
7
root
root
root
parents
1→null
2→1
3→1
4→2
5→2
6→3
7→3
queue
forest
6
7
1
return [6, 7, 1]
algo
master
.
io
Step:
Start: delete [3,5] with two BFS passes, one to record every node's parent and one to perform the deletions
0 / 42
Input
Example 1
Example 2
Example 3
Custom
tree
=
[1, 2, 3, 4, 5, 6, 7]
,
toDelete
=
[3, 5]
0 / 42
algo
master
.
io
Step:
Start: delete [3,5] with two BFS passes, one to record every node's parent and one to perform the deletions
