Data Structures: Trees
Trees -> Concepts
Haven’t you ever realised how our operating system quietly manages our files? Why do we have a hierarchical file system? How our files get saved under hierarchical directories? Well, answer to all that is Trees!
Tree is a data structure which allows you to associate a parent-child relationship between various pieces of data and thus allows us to arrange our records, data and files in a hierarchical fashion.
Assume a Tree representing your family structure. Let say we start with your Grand parent; then come to your parent and finally, you and your siblings. Refer this Tree below to understand better.
As you can see, the top most element is called the “root”. The nodes with no children are called “Leaf” nodes. Here, if I say “D” is representing you then “E” becomes your sibling; “B” becomes your parent; “A” becomes your ancestor (grand parent) and “C” is sibling of your parent. If I call A as the root then B onwards is one sub tree and C onwards is another. A sub-tree can have zero or more sub-trees in it.
Every tree has a depth and height factor associated. These factors are associated with every node in the tree. The depth of a particular node tells you how many generations down, that node is from the Root. Similarly, height of a particular node tells you its distance from the deepest leaf (or leaves) in that branch (or sub tree). For example — D and E are at height = 0; C is at height = 0; and A is at height = 2. The height of a Tree is nothing but the height of its root. Both of these factors have their own importance at times.
Any Tree whose nodes can have at the most two children is called a Binary tree or a tree with order 2. I’ll stress on this only, as unlike trees with higher orders, this has got a definite analysis.
Every node in a Binary tree has a structure like this -
Struct NODE
{
struct NODE *leftchild;
Int nodevalue; /*this can be of any type*/
struct NODE *rightchild;
}…and it looks like this -
Note:- Although there are trees with more than two children, I have covered mostly the concepts in Trees which concern a Binary tree only.
Trees -> Binary Tree Creation
The binary tree creation follows a very simple principle — for the new element to be added, compare it with the current element in the tree. If its value is less than the current element in the tree then move towards the left side of that element or else to its right. If there is no sub tree on the left, make your new element as the left child of that current element or else compare it with the existing left child and follow the same rule. Exactly same has to done for the case when your new element is greater than the current element in the tree but this time with the right child. Check out the algo..
Algorithm:-
Step-1: If Value of New element < current element then go to step-2 or else step-3
Step-2: If the Current element does not have a left sub-tree then make your new element the left child of the current element; else make the existing left child as your current element and go to step-1
Step-3: If the current element does not have a right sub-tree then make your new element the right child of the current element; else make the existing right child as your current element and go to step-1
C implementation:-
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
}
create_tree( struct NODE *curr, struct NODE *new )
{
if(new->value <= curr->value)
{
if(curr->left != NULL)
create_tree(curr->left, new);
else
curr->left = new;
}
else
{
if(curr->right != NULL)
create_tree(curr->right, new);
else
curr->right = new;
}
}Trees -> Traversals
We have seen traversal of graphs — DFS and BFS. Similarly, when we want to visit each and every element of a tree, there are three different ways to do the traversal — preorder, inorder and postorder. Remember, these traversal methods are limited to Binary trees only and not for any other tree.
As you know every tree-node has a leftchild-link :: Value-field :: rightchild-link structure, in INORDER traversal, for every node in the tree we first visit its left sub-tree (if its there); then visit the node itself; and then the right sub-tree (if its there). Follow the example -
We start from the root i.e A. We are supposed to visit its left sub-tree then visit the node itself and its right sub-tree. Here, A has a left sub-tree rooted at B. So, I move to B and check for its left sub-tree (as I’m supposed to do it for every node). Again, B has a left sub-tree rooted at D. So, I check for D’s left sub-tree now, but D doesn’t have any left sub-tree and thus I’ll visit node D first and check for its right sub-tree. As D doesn’t have any right sub-tree, we’ll track back and visit node B; and check for its right sub-tree. B has a right sub-tree rooted at E and so we move to E. Well, E doesn’t have any left or right sub-trees so we just visit E and track back to B. We already have visited B, so we track back to A. We are yet to visit the node itself and so we visit A first; then we go for checking the right sub-tree of A, which is rooted at C. As C doesn’t have any left or right tree we visit C. So, the INORDER becomes — D B E A C
Similarly, in PREORDER, we visit the current node first, then we visit its left sub-tree and then its right sub-tree. In POSTORDER, for every node, we visit the left sub-tree first and then the right sub-tree and finally the node itself.
Algorithm:-
Step-1: For the current node check whether it has a left child. If it has then go to step-2 or
else step-3
Step-2: Repeat step-1 for this left child
Step-3: Visit (i.e printing in our case) the current node
Step-4: For the current node check whether it has a right child. If it has then go to step-5
Step-5: Repeat step-1 for this right child
Get Akash Nath’s stories in your inbox
Join Medium for free to get updates from this writer.
This is the recursive algorithm for INORDER traversal.
C implementation:-
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
}
inorder(struct NODE *curr)
{
if(curr->left != NULL) inorder(curr->left); /*step-1 & step-2*/
printf("%d", curr->value); /*step-3*/
if(curr->right != NULL) inorder(curr->right); /*step-4*/
}Trees -> Threaded Binary Tree -> Concepts
A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor. By doing this threading we avoid the recursive method of traversing a Tree, which makes use of stacks and consumes a lot of memory and time.
The node structure for a threaded binary tree varies a bit and its like this —
struct NODE
{
struct NODE *leftchild;
int node_value;
struct NODE *rightchild;
struct NODE *thread;
}Let’s make the Threaded Binary tree out of a normal binary tree…
The INORDER traversal for the above tree is — D B A E C. So, the respective Threaded Binary tree will be —
B has no right child and its inorder successor is A and so a thread has been made in between them. Similarly, for D and E. C has no right child but it has no inorder successor even, so it has a hanging thread. Clear!
Trees -> Non-recursive traversal using a Threaded Binary Tree
As this is a non-recursive method for traversal, it has to be an iterative procedure; meaning, all the steps for the traversal of a node have to be under a loop so that the same can be applied to all the nodes in the tree.
I’ll consider the INORDER traversal again. Here, for every node, we’ll visit the left sub-tree (if it exists) first (if and only if we haven’t visited it earlier); then we visit (i.e print its value, in our case) the node itself and then the right sub-tree (if it exists). If the right sub-tree is not there, we check for the threaded link and make the threaded node the current node in consideration. Please, follow the example given below.
Algorithm:-
Step-1: For the current node check whether it has a left child which is not there in the visited list. If it has then go to step-2 or else step-3.
Step-2: Put that left child in the list of visited nodes and make it your current node in consideration. Go to step-6.
Step-3: For the current node check whether it has a right child. If it has then go to step-4 else go to step-5
Step-4: Make that right child as your current node in consideration. Go to step-6.
Step-5: Check for the threaded node and if its there make it your current node.
Step-6: Go to step-1 if all the nodes are not over otherwise quit
C implementation:-
struct NODE
{
struct NODE *left;
int value;
struct NODE *right;
struct NODE *thread;
}
inorder(struct NODE *curr)
{
while(all the nodes are not over )
{
if(curr->left != NULL && ! visited(curr->left))
{
visit(curr->left);
curr = curr->left;
}
else
{
printf("%d", curr->value);
if(curr->right != NULL)
curr = curr->right;
else
if(curr->thread != NULL)
curr = curr->thread;
}
}
}Note:- The looping condition has to be implemented. You can use your own logic for that. The functions — visited( ) and visit( ) have to be written. visit( ) maintains a linked list of already visited nodes. visited( ) returns a TRUE value if it finds a particular node, in the list maintained by visit( ), otherwise FALSE.
Link to other topics on Data Structures:
