Graph Theory | Rooting a Tree

Graph Theory | Rooting a Tree

Today, we are going to see how we can root a tree. This is the 8th post of my ongoing series Graph Theory : Go Hero . You should definitely check out the index page to deep dive into Graphs and related problems. I mostly try to come up with new posts of this series in every weekends. Let’s see how rooting is done.

This is one of those very basic and fundamental transformations we need to have if we want to work with rooted trees. The motivation of rooting a tree is that often it can help to add a structure and simplify the problem. A rooted tree can convert an undirected tree into a directed one which lot more easier to work with. Conceptually, rooting a tree is like picking up the tree by a specific node and having all the edges point downwards.

We can root a tree by using any of it’s nodes, however be cautious about the node we are choosing because not all nodes would not generate well balanced trees. So we need to be a bit selective.

In some situations, it’s always a good idea to have a route back to the parent node so that we can walk back. I have illustrated routes to parent nodes with red lines below.

Let’s see how we can root a tree.

Rooting Solution

Rooting a tree is easily done with a Depth First Search ( DFS ). I have created an animated version of the resultant DFS below. You would definitely understand it, for sure.

and that’s rooting a tree in a nutshell.

Pseudo Code

class Treenode:

 int id;
 Treenode parent;
 Treenode [] children;function rootTree(g, rootId = 0):
 root = Treenode(rootId, null, [])
 return buildTree(g, root, null)function buildTree(g, node, parent):
 for child in g[node.id]:
 if parent != null and childId == parent.id:
 continue
 child = Treenode(childId, node, [])
 node.children.add(child)
 buildTree(g, child, node)
 return node

We have a class defined with name Treenode. Every node in the tree would have an unique id, that’s what we are storing in the id placeholder. As we discussed earlier, it’s always a best practice to save the parent node because it would help us to travel back. Also, we save some references to the children of the current node.

Then we define a function called rootTree which takes two parameters into it – a graph and the id of the node to get start. The graph g would be represented as an adjacency list with undirected edges. The first line of rootTree method creates a Treenode object with given rootId , parent reference and list of children. The rootTree function invokes another function named buildTree with paramters graph g, root node and reference to the parent node.

The buildTree method takes the exact three parameters we just talked about. As we enter into the function, we end up landing in a for loop which travels all over the children of the current node. We know the edges are undirected, so we absolutely need to manage the situation where we add a directed edge pointing towards the same node. If the above condition is not met, we are sure that we have a confirmed child in our hand. Then we create an object to the Treenode class and add the child to the list of children of the current node. Afterwards, it does DFS more into the tree using the newly created node. We return the current node as we visit all the neighbors of the node.

So, that’s how we root a tree. We will discuss about Tree center(s) in the coming post. Let’s keep learning, together.

Cheers all.