What would you like to Propose?

Centroid Decomposition is a divide and conquer technique for tree data structures. It repeatedly selects a centroid (a node whose removal splits the tree into balanced parts) and builds a centroid tree. This structure enables efficient handling of dynamic and distance based queries on trees.

This algorithm is not currently included in the repository, and adding it will expand the library of tree algorithms.

Issue details

Proposed Feature

Add a clean implementation of Centroid Decomposition for trees.

Files to be added

to com.thealgrithms.tree:

CentroidDecomposition.java
CentroidDecompositionTest.java

Plan

Construct centroid tree in O(N logN)

Provide clear API and documentation

Include JUnit tests for small trees and edge cases

Additional Information

I am working on this feature and will send a PR shortly. Happy to take feedback before or during development.