Tree and Tree Traversal (In Order / Pre Order / Post Order)

We extend the concept of linked data structures to structure containing nodes with more than one self-referenced field. A binary tree is made of nodes, where each node contains a "left" reference, a "right" reference, and a data element. The topmost node in the tree is called the root. Every node (excluding root) in a tree is connected by a directed edge from exactly one other node. This node is called a parent. On the other hand, each node can be connected to arbitrary number of nodes, called children. Nodes with no children are called leaves, or external nodes. Nodes which are not leaves are called internal nodes. Nodes with the same parent are called siblings. One example of creation of binary tree is given below Fig2.

---

Tree terminologies

---

• The depth of a node is the number of edges from the root to the node.
• The height of a node is the number of edges from the node to the deepest leaf.
• The height of a tree is a height of the root.
• A leaf node which does not have any child node.
• The child nodes of a given parent node are called siblings.
• A strictly binary tree.is a binary tree in which each node has exactly zero or two children.
• A complete binary tree is a binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right.

---

Properties of Binary tree

---

1. The number of external nodes is 1 more than the number of internal nodes. It is easy to see this if we start removing external nodes with their internal parent, one pair at a time. At the end of this process only the root with its two children will remain.
2. The number of external nodes is at least h+1, where h is the height of the tree, and at most 2h. The later holds for a full binary tree, which is a tree where internal nodes completely fill every level.
3. The number of nodes is at least h and at most 2^h-1.
4. A binary tree with n nodes has exactly n-1 edges.

---

Height of a Binary Tree

---

We know that binary tree with height h can have no more 2^h-1 elements. Thus if n is the total number of nodes then
n <= 2^h-1
n+1 <= 2^h
log n+1 <= log 2^h
log n+1 <= h*log 2
log n+1 <= h*1
h >= log n+1

---

Representation Of a Binary Tree

---

Binary tree can be represented either using array or using linked list. In case of array implementation tree can be stored sequentially i.e. a block of memory is to be allocated before going to store the actual tree in it. The following rules are used to decide the location of any node:

The root node is at location 1 and for any other node with index i,1 < i <= n, parent(i)=i/2; left child(i)=2i and right child(i)=2i+1.The advantage of using array is there is no pointer and node can be accessed through index. But it is not suitable to use because insertion and deletion creates more data movements. So we go for another method i.e. linked representation. In the next topics readers will find how to represent tree in linked format.

Inorder Traversal	In a inorder traversal, work at a node is performed after processing it's left child and before processing it's right child. For example, inorder traversal is:D B F E A G C K J H L which is shown in Fig 1.
Preorder Traversal	In a preorder traversal, work at a node is performed before (pre) its children are processed. For example, preorder traversal is: A B D E F C G H J K L which is shown in Fig 1.
Postorder Traversal	In a postorder traversal, the work at a node is performed after (post) its children are evaluated. For example, postorder traversal is: D F E B G K J L H C which is shown in Fig 1.

Now as we have familiar with traversal of binary tree we will construct the tree from different traversals. Here we will consider two cases.

Case 1:

In order: E A K C F H D B G

Pre order: F A E C K D H G B

How to construct tree from these two traversal is given below in following Fig 2.

Fig. construct tree form inorder-preorder traversal

Post order: H D I E B J F K L G C A

In order: H D B I E A F J C K G L

How to construct tree from these two traversal is given below in following Fig 3.

Source code is given below to construct tree from different traversal.

Creating Tree From Different Traversal

#include <stdio.h> #include <stdlib.h> #define MAX 50 struct node { int data; struct node* left; struct node* right; }; int search(int *arr, int , int , int ); struct node* newNode(int data); /* Recursive function to construct binary of size len from Inorder traversal in[] and Preorder traversal pre[]. */ struct node* buildTree(int *in, int *pre, int inStart, int inEnd) { static int preIndex = 0; if(inStart > inEnd) return NULL; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ struct node *tNode = newNode(pre[preIndex++]); /* If this node has no children then return */ if(inStart == inEnd) return tNode; /* Else find the index of this node in Inorder traversal */ int inIndex = search(in, inStart, inEnd, tNode->data); /* Using index in Inorder traversal, construct left and right subtress */ tNode->left = buildTree(in, pre, inStart, inIndex-1); tNode->right = buildTree(in, pre, inIndex+1, inEnd); return tNode; } /* when we consider inorder and postorder traversal*/ struct node* buildTree1(int *in, int *post, int inStart, int inEnd,int postStart,int postEnd) { if(inStart > inEnd || postStart>postEnd) return NULL; int rootValue=post[postEnd]; /* Pick current node from Preorder traversal using preIndex and increment preIndex */ struct node *tNode = newNode(rootValue); /* find the index of this node in Inorder traversal */ int inIndex = search(in, inStart, inEnd, rootValue); /* Using index in Inorder traversal, construct left and right subtress */ tNode->left = buildTree1(in, post, inStart, inIndex-1,postStart,postStart+inIndex-(inStart+1)); tNode->right = buildTree1(in, post, inIndex+1, inEnd,postStart+inIndex-inStart,postEnd-1); return tNode; } /* Function to find index of value in arr[start...end] The function assumes that value is present in in[] */ int search(int *arr, int start, int end, int value) { int i; for(i = start; i <= end; i++) { if(arr[i] == value) return i; } } /* function that allocates a new node with the given data and NULL left and right pointers. */ struct node* newNode(int data) { struct node* node = (struct node*)malloc(sizeof(struct node)); node->data = data; node->left = NULL; node->right = NULL; return(node); } /* This funtcion is here just to test buildTree() */ void printpostorder(struct node* node) { if (node == NULL) return; /* first recur on left child */ printpostorder(node->left); /* now recur on right child */ printpostorder(node->right); /* then print the data of node */ printf("%d|", node->data); } void printpreorder(struct node* node) { if (node == NULL) return; /* print data of node */ printf("%d|",node->data); /* now recur on left child */ printpreorder(node->left); /* now recur on right child */ printpreorder(node->right); } int main() { int *in,*pre,*post; int i,n,len,ch,j,temp; in=(int *)malloc(sizeof(int)*MAX); pre=(int *)malloc(sizeof(int)*MAX); post=(int *)malloc(sizeof(int)*MAX); while(1) { printf("\n1.inorder and preorder traversal is given"); printf("\n2.inorder and postorder traversal is given"); printf("\n3.exit"); printf("\nenter your choice:"); scanf("%d",&ch); switch(ch) { case 1: printf("\nEnter how many numbers you will put:"); scanf("%d",&n); printf("\nenter the inorder traversal:"); for(i=0;i < n;i++) scanf("%d",&in[i]); printf("\nenter the preorder traversal:"); for(i=0;i < n;i++) scanf("%d",&pre[i]); len=n; struct node *root = buildTree(in, pre, 0, len - 1); printf("\npostorder traversal of the constructed tree is:"); printpostorder(root); break; case 2: printf("\nEnter how many numbers you will put:"); scanf("%d",&n); printf("\nenter the inorder traversal:"); for(i=0;i < n;i++) scanf("%d",&in[i]); printf("\nenter the postorder traversal:"); for(i=0;i < n;i++) scanf("%d",&post[i]); len=n; struct node *rt = buildTree1(in, post,0,len-1,0,len-1); printf("\npreorder traversal of the constructed tree is:"); printpreorder(rt); break; case 3: return 0; } } return 0; }

---

Happy Exploring!