Rooting a tree at a specific node

Algorithms  #algorithms  #trees  #graphs 

Rooting a tree refers to the process of designating a node in a tree data structure as the root node.

A tree data structure is a collection of nodes connected by edges, where each node has zero or more child nodes, except for the root node, which has no parent node.

Algorithm

By performing DFS and keeping track of parent nodes, a tree can be rooted at any node.

1. Choose a starting node (the root node)
2. Keep track of parent nodes, i.e. where the current node is discovered, and perform DFS
3. Add each newly discovered node as a child of its parent
4. Continue until DFS is complete

Example

• The following script roots the tree given above at node 3

fun getExampleGraph(): List<List<Int>> {
    return 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(7, 6, 3))
        add(6, listOf(5))
        add(7, listOf(5))
    }
}

//sampleStart
fun main() {
    val adjacencyList = getExampleGraph()
    // root at node 3
    val root = Node(value = 3, parent = null, children = mutableListOf())
    rootAtNode(node = root, adjList = adjacencyList)
    printTree(root)
}

class Node(
        val value: Int,
        val parent: Node? = null,
        val children: MutableList<Node> = mutableListOf(),
)

fun rootAtNode(node: Node, adjList: List<List<Int>>) {
    // click + to see full script
    adjList[node.value].forEach { adjacentNode ->
        if (node.parent?.value != adjacentNode) {
            val childNode = Node(value = adjacentNode, parent = node)
            node.children.add(childNode)
            rootAtNode(childNode, adjList)
        }
    }
}
//sampleEnd

fun printTree(node: Node) {
    println("parent: ${node.value}, children: ${node.children.map { it.value }}")
    node.children.forEach(::printTree)
}

• Result

Advantages

1. Efficient search: Rooting a tree allows for efficient search algorithms, such as binary search trees and balanced search trees, which can reduce search time and improve overall efficiency.

2. Clear hierarchy: Rooting a tree establishes a clear hierarchy within the data structure, making it easier to understand and reason about the relationships between nodes and subtrees.

3. Easy traversal: Rooting a tree provides a clear starting point for traversal algorithms, such as depth-first search and breadth-first search, making it easier to navigate the tree and access the nodes in a desired order.

4. Reduces duplicate work: Rooting a tree can reduce the amount of duplicate work in certain algorithms. For example, in dynamic programming problems, rooting a tree can eliminate the need to recalculate solutions for the same subtree multiple times.

5. Other: Undirected edges can be converted to directed edges