Find center of a tree

Algorithms  #algorithms  #trees  #graphs 

The center of a tree is defined as the node or set of nodes that minimize the maximum distance to any other node in the tree.

A tree can have multiple centers.

There are two ways to find the center(s) of a tree.

1. Using the longest path
2. By finding the degree of nodes and removing the leaves

Method 1: Tree center(s) using the longest path

Center of the tree is always the middle or middle 2 vertices on the longest path of the tree.

• The following illustration finds the tree center using the longest path for the tree given above

Method 2: By finding the degree of nodes and removing the leaves

Another approach to finding the centre of a tree is to iteratively remove the leaf nodes.

Start by finding the degree of all nodes. The leaf nodes will have a degree of 1. Remove all leaf nodes and decrease the degree of adjacent nodes. Whenever the degree of the node become 1, remove it. Repeat the process (just like peeling an onion) until center(s) is reached i.e. only one or two nodes are left.

• The following example illustrates how to find tree center (by removing leaf nodes) in the above-mentioned tree

Example

• The following script finds the center of the tree (give above) by repeatedly removing leaf nodes

fun main() {
    val adjacencyList = mutableListOf<List<Int>>().apply {
        add(0, listOf(1, 2, 3))
        add(1, listOf(0))
        add(2, listOf(0))
        add(3, listOf(0, 4, 5))
        add(4, listOf(3))
        add(5, listOf(3))
    }
    getCenters(adjacencyList).also {
        println("Tree center(s): $it")
    }
}

//sampleStart
fun getCenters(adjacencyList: List<List<Int>>): List<Int> {
    // click + to see full script
    val degree = IntArray(adjacencyList.size)
    var leaves = mutableListOf<Int>()

    // find the degree of all nodes and add leaves to the list
    adjacencyList.indices.forEach { node ->
        degree[node] = adjacencyList[node].size
        val isLeafNode = degree[node] == 0 || degree[node] == 1
        if (isLeafNode) {
            leaves.add(node)
            degree[node] = 0
        }
    }

    // repeatedly remove the leaves and update the degree of adjacent nodes
    val noOfNodes = adjacencyList.size
    var currentLeaveCount = leaves.size

    while (currentLeaveCount < noOfNodes) {
        val newLeaves = mutableListOf<Int>()
        leaves.forEach { leafNode ->
            adjacencyList[leafNode].forEach { adjacentNode ->
                degree[adjacentNode]--
                // add adjacent node to leave if degree became 0 after update
                if (degree[adjacentNode] == 1) {
                    newLeaves.add(adjacentNode)
                }
            }
            degree[leafNode] = 0
        }
        currentLeaveCount += newLeaves.size
        leaves = newLeaves
    }
    return leaves
}
//sampleEnd

Advantages

1. Efficient routing: The center of a tree can be used as a central point for efficient routing in communication networks. This is because the center minimizes the maximum distance between any two nodes in the tree, which helps reduce the number of hops required to transmit messages between nodes.

2. Load balancing: By identifying the center of a tree, it is possible to balance the load of the tree, ensuring that each node has an approximately equal number of descendants. This can help to improve the overall performance and stability of the tree.

3. Tree visualization: Identifying the center of a tree can help in visualizing the structure of the tree. This can help to better understand the hierarchical relationships between nodes and the overall shape of the tree.

4. Root selection: In some cases, it may be desirable to select a central node as the root of the tree. By identifying the center of the tree, it is possible to select a node that is close to the majority of the other nodes, which can help to reduce the height of the tree and improve its overall balance.