Rooting a tree | Graph Theory

Key Takeaways

[Music] hello and welcome my name is William and today we're having a look at how to root a tree this is one of those very basic fundamental transformations that's handy to have in your tool kit in case you want to or need to work with a rooted tree the motivation for rooting a tree is that often it can help to add structure and simplify the problem you're trying to solve routing a tree enables you to easily perform recursive algorithms it also transforms the tree to have directed edges instead of undirected edges which are generally a lot easier to work with conceptually routing a tree is like picking up a tree by a specific node and having all the edges point downwards you can retreat using any of its nodes however be cautious because not every node you select will result in a well balanced tree and if that's your objective you may need to be a little bit more selective in some situations it's also useful to have a reference to the parent node in order to be able to walk up the tree I Allah strated parent node pointers as dotted lines on this slide let's have a look at an example of how to route a tree one of the best ways to do this is with a depth-first search through the original tree and to create the rooted tree during the traversal the algorithm starts on the designated root node the new rooted tree is being displayed on the right from the root node begin the depth-first search and add notes to the rooted tree as the algorithm proceeds I will let the animation play and it should be clear what's going on you and that's ruining a tree in a nutshell let's have a look at some pseudocode for this on this slide I define a tree node object which we will use to store one of the nodes of our tree each node has a unique integer ID to identify the node as well as a reference to its parent pointer this member is generally optional but I thought to include it for completeness taking note that every node will have a parent pointer except for the root node whose parent pointer will be null additionally each node also has a list of all its child and nodes here's the algorithm to root a tree it's relatively short and sweet the input to the root tree function takes a graph G as input which is the tree we want to route the other input is the ID of the designated root node by default this is node 0 but it can be any other node the first line of the root tree method creates the root tree node object with the ID route ID a parent reference of null and no child nodes then I call the build tree method to start the depth first search reversal to root the tree as input parameters I pass in the graph G the root node as the current node and the roots parent which is null the build tree method takes exactly the same parameters we just talked about the graph the current node and the current nodes parent node reference next we enter a for loop that loops over all the neighbors of the current node which in turn will become the children of the current node because edges are undirected in the original tree we absolutely need to avoid the situation where we add a directed edge pointing back to the current nodes parent first check that the parent is not null so we don't get a null pointer exception when we're trying to access the parents ID then check if the child is equal to the parent ID and skip this note if this is true otherwise we're dealing with a proper child note so create a new node and add the child tree node to the list of the current nodes children afterwards dig deeper depth the first into the tree and do the same thing but for the newly created child node once we've finished iterating over all the neighbors of this node returned the current node and that's how you root a tree all right thank you for watching please give this video a thumbs up if you learn something and subscribe for more mathematics and computer science videos