Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Centroid Decomposition
Bookmark
Input
Standard Tree (7 nodes)
Path Graph (5 nodes)
Star Graph (7 nodes)
Balanced Binary Tree (9 nodes)
Custom
n
=
7
,
edges
=
[[0,1],[1,2],[1,3],[3,4],[3,5],[5,6]]
Original Tree
Original Tree
0
1
2
3
4
5
6
CD Tree
(builds as centroids are found)
Legend:
Unprocessed
Component
Centroid
Removed
Original Tree
Original Tree
0
1
2
3
4
5
6
CD Tree
(builds as centroids are found)
Legend:
Unprocessed
Component
Centroid
Removed
Removed centroid 3 (root of CD tree)
Original Tree
0
1
2
3
4
5
6
CD Tree
3
Legend:
Unprocessed
Component
Centroid
Removed
Found centroid: node 1
Original Tree
0
1
2
3
4
5
6
CD Tree
3
Legend:
Unprocessed
Component
Centroid
Removed
Computing subtree sizes (component size = 1)
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
Legend:
Unprocessed
Component
Centroid
Removed
Recursing into subtree containing node 2 (1 nodes)
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
Legend:
Unprocessed
Component
Centroid
Removed
Recursing into subtree containing node 4 (1 nodes)
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
2
Legend:
Unprocessed
Component
Centroid
Removed
Removed centroid 4, parent in CD tree: 3
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
2
4
Legend:
Unprocessed
Component
Centroid
Removed
Found centroid: node 5
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
2
4
Legend:
Unprocessed
Component
Centroid
Removed
Computing subtree sizes (component size = 1)
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
2
4
5
Legend:
Unprocessed
Component
Centroid
Removed
Centroid Decomposition Complete
Original Tree
0
1
2
3
4
5
6
CD Tree
3
1
0
2
4
5
6
CD Parent: 0->1, 1->3, 2->1, 3->root, 4->3, 5->3, 6->5
Legend:
Unprocessed
Component
Centroid
Removed
algo
master
.
io
Step:
Start: Centroid Decomposition of the tree
0 / 28
Input
Standard Tree (7 nodes)
Path Graph (5 nodes)
Star Graph (7 nodes)
Balanced Binary Tree (9 nodes)
Custom
n
=
7
,
edges
=
[[0,1],[1,2],[1,3],[3,4],[3,5],[5,6]]
0 / 28
algo
master
.
io
Step:
Start: Centroid Decomposition of the tree
