Traversal of binary tree

Traversal of binary tree: A node is visited only once in the traversal of the binary tree. There are three main types of traversal methods in the binary tree.

1. In-order traversal
2. Pre-order traversal
3. Post-order traversal

In-order traversal: 

In the in-order traversal method, the left child and left subtree are traversed first, afterward the root tree and then the right children or the right subtree are traversed.

Algorithm of In-order traversal

In-order-traversal (tree)
Step 1: Start with left sub-tree      // call In-order (left subtree) 
Step 2: Then, root tree 
Step 3: And then, right sub-tree    // call In-order (right subtree)

Example: Find the in-order traversal for this tree.

Solution.

Step 1: Left sub-tree is 1 ? 4 ? 9

Step 2: Root node is 5

Step 3: Right sub-tree is 5 ? 7 ? 2 ? 6 ? 3    

In-order Traversal = 1 ? 4 ? 9 ? 5 ? 5 ? 7 ? 2 ? 6 ? 3

Pre-order Traversal:

In the pre-order traversal method, the root node is traversed first, then the left subtree, and then the right subtree is traversed.

Algorithm of pre-order traversal

Pre-order-traversal (tree) 
Step 1: Start with the root node    
Step 2: Then, the left sub-tree       // call Pre-order (left subtree) 
Step 3: And then, right sub-tree    // call Pre-order (right subtree)

Example: Find the pre-order traversal for this tree.

Solution.

 Step 1: Root node is 5

Step 2: Left sub-tree is 4 ? 1 ? 9

Step 3: Right sub-tree is 6 ? 7 ? 5 ? 2 ? 3    

Pre-order Traversal = 5 ? 4 ? 1 ? 9 ? 6 ? 7 ? 5 ? 2 ? 3

Post-order traversal:

In the post-order traversal method, the left child and left subtree are traversed first, then the right subtree is traversed, and then the root node.

Algorithm of Post-order traversal

Post-order-traversal (tree)
Step 1: Start with left sub-tree        // call Post-order (left subtree) 
Step 2: Then, right sub-tree           // call Post-order (right subtree) 
Step 3: And then, root tree

Example: Find the Post-order traversal for this tree.

Solution.

Step 1: Left sub-tree is 1 ? 9 ? 4
Step 2: Right sub-tree is 5 ? 2 ? 7 ? 3 ? 6
Step 3: Root node is 5    
Post-order Traversal = 1 ? 9 ? 4 ? 5 ? 2 ? 7 ? 3 ? 6 ? 5

Applications of binary tree

1. The binary search tree is used in many search applications.
2. Nowadays, a binary Space Partition is used for every 3D game.3.
3. The binary tree is used in every high bandwidth router that stores the router table.

Binary tree program in C language

// Binary Tree in C   
#include <stdio.h> 
#include <stdlib.h>   
struct node 
{   
int data;   
struct node *left;   
struct node *right; 
}; 
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); }   
void traversePreOrder(struct node *t)
 {  
 if (t != NULL) 
  {   
  printf(" %d", t->data);  
   traversePreOrder(t->left); 
    traversePreOrder(t->right); 
  } 
}  
 void traverseInOrder(struct node *t)
 {  
 if (t != NULL) 
  {    
 traverseInOrder(t->left); 
    printf(" %d", t->data);  
   traverseInOrder(t->right);
  }
 } 
  void traversePostOrder(struct node *t)
 {  
 if (t != NULL) 
  {    
 traversePostOrder(t->left); 
    traversePostOrder(t->right); 
    printf(" %d", t->data); 
  } 
}   
int main() 
{  
 struct node *root = newNode(1); 
  root->left = newNode(2);  
 root->right = newNode(3); 
  root->left->left = newNode(4); 
  printf("The preorder traversal of the tree is: "); 
  traversePreOrder(root);   
printf("\nThe inorder traversal of the tree is: "); 
  traverseInOrder(root);   
printf("\nThe postorder traversal of the tree is: ");  
 traversePostOrder(root); }