Binary Tree Traversal in Data Structure

The tree can be defined as a non-linear data structure that stores data in the form of nodes, and nodes are connected to each other with the help of edges. Among all the nodes, there is one main node called the root node, and all other nodes are the children of these nodes.

In any data structure, traversal is an important operation. In the traversal operation, we walk through the data structure visiting each element of the data structure at least once. The traversal operation plays a very important role while doing various other operations on the data structure like some of the operations are searching, in which we need to visit each element of the data structure at least once so that we can compare each incoming element from the data structure to the key that we want to find in the data structure. So like any other data structure, the tree data also needs to be traversed to access each element, also known as a node of the tree data structure.

There are different ways of traversing a tree depending upon the order in which the tree’s nodes are visited and the types of data structure used for traversing the tree. There are various data structures involved in traversing a tree, as traversing a tree involves iterating over all nodes in some manner.

As from a given node, there could be more than one way to traverse or visit the next node of the tree, so it becomes important to store one of the nodes traverses further and store the rest of the nodes having a possible path for backtracking the tree if needed. Backtracking is not a linear approach, so we need different data structures for traversing through the whole tree. The stack and queue are the major data structure that is used for traversing a tree.

Traversal is a technique for visiting all of a tree’s nodes and printing their values. Traversing a tree involves iterating over all nodes in some manner. We always start from the root (head) node since all nodes are connected by edges (links). As the tree is not a linear data structure, there can be more than one possible next node from a given node, so some nodes must be deferred, i.e., stored in some way for later visiting.

Types of Traversal of Binary Tree

There are three types of traversal of a binary tree.

Inorder tree traversal
Preorder tree traversal
Postorder tree traversal

Inorder Tree Traversal

The left subtree is visited first, followed by the root, and finally the right subtree in this traversal strategy. Always keep in mind that any node might be a subtree in and of itself. The output of a binary tree traversal in order produces sorted key values in ascending order.

C Code

Let’s write a basic C program for Inorder traversal of the binary search tree.

  //C Program for Inorder traversal of the binary search tree     #include  #include    struct node  {      int key;      struct node *left;      struct node *right;  };    //return a new node with the given value  struct node *getNode(int val)  {      struct node *newNode;        newNode = malloc(sizeof(struct node));        newNode->key   = val;      newNode->left  = NULL;      newNode->right = NULL;        return newNode;  }    //inserts nodes in the binary search tree  struct node *insertNode(struct node *root, int val)  {       if(root == NULL)           return getNode(val);         if(root->key < val)           root->right = insertNode(root->right,val);         if(root->key > val)           root->left = insertNode(root->left,val);         return root;  }    //inorder traversal of the binary search tree  void inorder(struct node *root)  {      if(root == NULL)          return;        //traverse the left subtree      inorder(root->left);        //visit the root      printf(“%d “,root->key);        //traverse the right subtree      inorder(root->right);  }    int main()  {     struct node *root = NULL;          int data;      char ch;          /*  Do while loop to display various options to select from to decide the input  */          do              {              printf(“nSelect one of the operations::”);              printf(“n1. To insert a new node in the Binary Tree”);              printf(“n2. To display the nodes of the Binary Tree(via Inorder Traversal).n”);                int choice;              scanf(“%d”,&choice);                          switch (choice)              {              case 1 :                   printf(“nEnter the value to be insertedn”);                  scanf(“%d”,&data);                  root = insertNode(root,data);                                    break;                                        case 2 :                   printf(“nInorder Traversal of the Binary Tree::n”);                  inorder(root);                  break;               default :                   printf(“Wrong Entryn”);                  break;                 }                printf(“nDo you want to continue (Type y or n)n”);              scanf(” %c”,&ch);                                  } while (ch == ‘Y’|| ch == ‘y’);       return 0;  }  

Output

The above C code hives the following output.

Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree (via Inorder Traversal).  1    Enter the value to be inserted  12    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  1    Enter the value to be inserted  98    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  1    Enter the value to be inserted  23    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  1    Enter the value to be inserted  78    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  1    Enter the value to be inserted  45    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  1    Enter the value to be inserted  87    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Inorder Traversal).  2    Inorder Traversal of the Binary Tree::  12 23 45 78 87 98   Do you want to continue (Type y or n)  n

Preorder Tree Traversal

In this traversal method, the root node is visited first, then the left subtree, and finally the right subtree.

Code

Let’s write a C code for the Preorder traversal of the binary search tree.

  /*   * Program: Preorder traversal of the binary search tree   * Language: C   */    #include  #include    struct node  {      int key;      struct node *left;      struct node *right;  };    //return a new node with the given value  struct node *getNode(int val)  {      struct node *newNode;        newNode = malloc(sizeof(struct node));        newNode->key   = val;      newNode->left  = NULL;      newNode->right = NULL;        return newNode;  }    //inserts nodes in the binary search tree  struct node *insertNode(struct node *root, int val)  {       if(root == NULL)           return getNode(val);         if(root->key < val)           root->right = insertNode(root->right,val);         if(root->key > val)           root->left = insertNode(root->left,val);         return root;  }    //preorder traversal of the binary search tree  void preorder(struct node *root)  {      if(root == NULL)          return;        //visit the root      printf(“%d “,root->key);        //traverse the left subtree      preorder(root->left);        //traverse the right subtree      preorder(root->right);  }    int main()  {     struct node *root = NULL;       int data;      char ch;          /*  Do while loop to display various options to select from to decide the input  */          do              {              printf(“nSelect one of the operations::”);              printf(“n1. To insert a new node in the Binary Tree”);              printf(“n2. To display the nodes of the Binary Tree(via Preorder Traversal).n”);                int choice;              scanf(“%d”,&choice);                          switch (choice)              {              case 1 :                   printf(“nEnter the value to be insertedn”);                  scanf(“%d”,&data);                  root = insertNode(root,data);                                    break;                                        case 2 :                   printf(“nPreorder Traversal of the Binary Tree::n”);                  preorder(root);                  break;               default :                   printf(“Wrong Entryn”);                  break;                 }                printf(“nDo you want to continue (Type y or n)n”);              scanf(” %c”,&ch);                                  } while (ch == ‘Y’|| ch == ‘y’);         return 0;  }  

Output:

Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  45    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  53    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  1    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  2    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  97    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  22    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  2    Preorder Traversal of the Binary Tree::  45 1 2 22 53 97   Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  76    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  30    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  67    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  1    Enter the value to be inserted  4    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  2    Preorder Traversal of the Binary Tree::  45 1 2 22 4 30 53 97 76 67   Do you want to continue (Type y or n)  n

Postorder Tree Traversal

The root node is visited last in this traversal method, hence the name. First, we traverse the left subtree, then the right subtree, and finally the root node.

Code

Let’s write a program for Postorder traversal of the binary search tree.

  /*   * Program: Postorder traversal of the binary search tree   * Language: C   */    #include  #include    struct node  {      int key;      struct node *left;      struct node *right;  };    //return a new node with the given value  struct node *getNode(int val)  {      struct node *newNode;        newNode = malloc(sizeof(struct node));        newNode->key   = val;      newNode->left  = NULL;      newNode->right = NULL;        return newNode;  }  //inserts nodes in the binary search tree  struct node *insertNode(struct node *root, int val)  {       if(root == NULL)           return getNode(val);         if(root->key < val)           root->right = insertNode(root->right,val);         if(root->key > val)           root->left = insertNode(root->left,val);         return root;  }    //postorder traversal of the binary search tree  void postorder(struct node *root)  {      if(root == NULL)          return;        //traverse the left subtree      postorder(root->left);        //traverse the right subtree      postorder(root->right);        //visit the root      printf(“%d “,root->key);  }  int main()  {     struct node *root = NULL;            int data;      char ch;          /*  Do while loop to display various options to select from to decide the input  */          do              {              printf(“nSelect one of the operations::”);              printf(“n1. To insert a new node in the Binary Tree”);              printf(“n2. To display the nodes of the Binary Tree(via Postorder Traversal).n”);                int choice;              scanf(“%d”,&choice);                          switch (choice)              {              case 1 :                   printf(“nEnter the value to be insertedn”);                  scanf(“%d”,&data);                  root = insertNode(root,data);                                    break;                                        case 2 :                   printf(“nPostorder Traversal of the Binary Tree::n”);                  postorder(root);                  break;               default :                   printf(“Wrong Entryn”);                  break;                 }                printf(“nDo you want to continue (Type y or n)n”);              scanf(” %c”,&ch);                                  } while (ch == ‘Y’|| ch == ‘y’);       return 0;  }  

Output:

Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  12    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  31    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  24  Wrong Entry    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  24    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  88    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  67    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  56    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  90    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  44    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  71    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  38    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  29    Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Postorder Traversal).  2    Postorder Traversal of the Binary Tree::  29 24 38 44 56 71 67 90 88 31 12   Do you want to continue (Type y or n)  n

We have seen the different C programs to implement inorder, preorder, and postorder traversal of the nodes of the Binary tree. Now let us write a code to perform all three types of traversal in a single program.

Code

  //Binary tree traversal:     #include   // #include   #include   struct node  {      struct node *left;      int data;      struct node *right;  };     void main()  {      void insert(struct node **,int);      void inorder(struct node *);      void postorder(struct node *);      void preorder(struct node *);         struct node *ptr = NULL;      int no,i,num;         // ptr = NULL;      // ptr->data=0;            int data;      char ch;          /*  Do while loop to display various options to select from to decide the input  */          do              {              printf(“nSelect one of the operations::”);              printf(“n1. To insert a new node in the Binary Tree”);              printf(“n2. To display the nodes of the Binary Tree(via Preorder Traversal).”);              printf(“n3. To display the nodes of the Binary Tree(via Inorder Traversal).”);              printf(“n4. To display the nodes of the Binary Tree(via Postorder Traversal).n”);                int choice;              scanf(“%d”,&choice);                          switch (choice)              {              case 1 :                   printf(“nEnter the value to be insertedn”);                  scanf(“%d”,&data);                  insert(&ptr,data);                                    break;                                        case 2 :                   printf(“nPreorder Traversal of the Binary Tree::n”);                  preorder(ptr);                  break;              case 3 :                   printf(“nInorder Traversal of the Binary Tree::n”);                  inorder(ptr);                  break;              case 4 :                   printf(“nPostorder Traversal of the Binary Tree::n”);                  postorder(ptr);                  break;               default :                   printf(“Wrong Entryn”);                  break;                 }                printf(“nDo you want to continue (Type y or n)n”);              scanf(” %c”,&ch);                                  } while (ch == ‘Y’|| ch == ‘y’);               // printf(“nProgram for Tree Traversaln”);      // printf(“Enter the number of nodes to add to the tree.<br>n”);      // scanf(“%d”,&no);         // for(i=0;ileft = NULL;          (*p)->right = NULL;          (*p)->data = num;          return;      }      else      {          if(num==(*p)->data)          {              printf(“nREPEATED ENTRY ERROR VALUE REJECTEDn”);              return;          }          if(num<(*p)->data)          {              printf(“nDirected to left link.n”);              insert(&((*p)->left),num);          }          else          {              printf(“Directed to right link.n”);              insert(&((*p)->right),num);          }      }      return;  }     void inorder(struct node *p)  {      if(p!=NULL)      {          inorder(p->left);          printf(“%d “,p->data);          inorder(p->right);      }      else      return;  }     void preorder(struct node *p)  {      if(p!=NULL)      {          printf(“%d “,p->data);          preorder(p->left);          preorder(p->right);      }      else      return;  }     void postorder(struct node *p)  {      if(p!=NULL)      {          postorder(p->left);          postorder(p->right);          printf(“%d “,p->data);      }      else      return;  }  ;i++)>

Output:

Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  2  Leaf node created.  Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  5  Directed to right link.  Leaf node created.  Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  7  Directed to right link.  Directed to right link.  Leaf node created.  Do you want to continue (Type y or n)  Y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  9  Directed to right link.  Directed to right link.  Directed to right link.  Leaf node created.  Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  31  Directed to right link.  Directed to right link.  Directed to right link.  Directed to right link.  Leaf node created.  Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  1    Enter the value to be inserted  78  Directed to right link.  Directed to right link.  Directed to right link.  Directed to right link.  Directed to right link.  Leaf node created.  Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  2    Preorder Traversal of the Binary Tree::  2 5 7 9 31 78   Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  3    Inorder Traversal of the Binary Tree::  2 5 7 9 31 78   Do you want to continue (Type y or n)  y    Select one of the operations::  1. To insert a new node in the Binary Tree  2. To display the nodes of the Binary Tree(via Preorder Traversal).  3. To display the nodes of the Binary Tree(via Inorder Traversal).  4. To display the nodes of the Binary Tree(via Postorder Traversal).  4    Postorder Traversal of the Binary Tree::  78 31 9 7 5 2   Do you want to continue (Type y or n)  n

Conclusion

So, in this article, we understood the binary tree traversal and different types of binary tree traversal like inorder binary tree traversal, preorder binary tree traversal, and postorder binary tree traversal. And we also did the programming implementation of all these types of tree traversal. And in the last part of the article, we also understood how to implement a basic c program that can be used to implement all three types of tree traversals in a single file.

Next TopicQueue Operations in Data Structure

Binary Tree Traversal in Data Structure

Binary Tree Traversal in Data Structure

Types of Traversal of Binary Tree

Inorder Tree Traversal

Preorder Tree Traversal

Postorder Tree Traversal

Conclusion

Apriori Algorithm

DS Circular Queue

You may also like