# Rooted Trees One of the more interesting types of a trees is a **rooted tree** which is a tree with a designated **root node.**  Most rooted trees have directed edges that point away from the root node. We can think of this root node and the edges pointing away from it as providing us with a *well defined structure* that we can design algorithms to take advantage of. Taking a step back, from a "meta" standpoint, this is an example of where we take advantage of *information* and *constraints* of a system to design *algorithms/representations/computations* that exploit this structure. This is a common theme that arises in mathematics and computer science; we try and determine the constraints of the system that we are working within, and then try to deduce what those constraints may allow us to say. As a super basic example of this, imagine that I tell you that I have a tree, $T$, that is rooted and directed away from the root node. If I then ask you: "Determine the number of edges pointed towards the root node", you do not need to investigate/compute anything! The structure and constraints that I told you were placed on $T$ already encode the answer (which is clearly $0$). ### Storing Rooted Trees We have seen a rough overview of how to [represent trees](Representing-Trees.md), but rooted trees are most naturally defined *recursively* in a top-down manner. In practice we always maintain a pointer reference to the *root node* and its contents:  Then, each node also has access to a list of all its *children*. For instance, below the orange node is the current node and the purple nodes are its children (the leaf nodes have no children).  It is also useful to maintain a pointer to a node's *parent node* (in case we need to traverse up the tree), effectively making edges **bidirectional**:  However, in practice maintaining an explicit reference to the parent isn't usually necessary because you can access a node's parent on a recursive function's callback as you pop frames off the stack. ### If the rooted tree is a binary tree... If our rooted tree is also a [binary tree](Binary%20Trees.md), we can store it as a flattened array! Here, each node has an assigned index position based on where it is in the tree!  The key to understand here is that the tree is actually an *array*! The diagrams are just a visual representation. The reason that this works is because we have an entry in out list representation *even if* a node doesn't exist, as show below:  We need to do this to ensure that we can define a *unique mapping* from our tree to the "index tree" (the grey tree). Notice that for *any* binary tree, our index tree will be *the same*! It is this structure that allows us to map our actual tree (blue, on left) to this index tree. In this format, the root node is always at index 0 in the array. The children of the current node, $i$, are accessed relative to position $i$. We can find the left and right child via: ```python # Find child nodes left node = 2*i + 1 right node = 2*i + 2 # Find parent parent_node = floor((i - 1) / 2) ``` As a quick example of this, consider the node with index `6` (on grey tree) above, that has a value of `2` (in blue tree). The child indices of this node are `13` and `14` and the parent is `2`. Does this match with our algorithm above? ```python # Our node index = 6 # Find child nodes left node = 2*6 + 1 = 13 right node = 2*6 + 2 = 14 # Find parent parent_node = floor((6 - 1) / 2) = 2 ``` We see that it does indeed work! --- Links to: [Trees](Trees.md) References