C++ Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree

«
»
This is a C++ Program to print inorder traversal of the given binary tree without using recursion.

Here is source code of the C++ Program to Perform Inorder Non-Recursive Traversal of a Given Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include<iostream>
  2. #include<conio.h>
  3. #include<stdlib.h>
  4. using namespace std;
  5. class node
  6. {
  7.     public:
  8.         class node *left;
  9.         class node *right;
  10.         int data;
  11. };
  12.  
  13. class tree: public node
  14. {
  15.     public:
  16.         int stk[50], top;
  17.         node *root;
  18.         tree()
  19.         {
  20.             root = NULL;
  21.             top = 0;
  22.         }
  23.         void insert(int ch)
  24.         {
  25.             node *temp, *temp1;
  26.             if (root == NULL)
  27.             {
  28.                 root = new node;
  29.                 root->data = ch;
  30.                 root->left = NULL;
  31.                 root->right = NULL;
  32.                 return;
  33.             }
  34.             temp1 = new node;
  35.             temp1->data = ch;
  36.             temp1->right = temp1->left = NULL;
  37.             temp = search(root, ch);
  38.             if (temp->data > ch)
  39.                 temp->left = temp1;
  40.             else
  41.                 temp->right = temp1;
  42.  
  43.         }
  44.  
  45.         node *search(node *temp, int ch)
  46.         {
  47.             if (root == NULL)
  48.             {
  49.                 cout << "no node present";
  50.                 return NULL;
  51.             }
  52.             if (temp->left == NULL && temp->right == NULL)
  53.                 return temp;
  54.  
  55.             if (temp->data > ch)
  56.             {
  57.                 if (temp->left == NULL)
  58.                     return temp;
  59.                 search(temp->left, ch);
  60.             }
  61.             else
  62.             {
  63.                 if (temp->right == NULL)
  64.                     return temp;
  65.                 search(temp->right, ch);
  66.  
  67.             }
  68.         }
  69.  
  70.         void display(node *temp)
  71.         {
  72.             if (temp == NULL)
  73.                 return;
  74.             display(temp->left);
  75.             cout << temp->data << " ";
  76.             display(temp->right);
  77.         }
  78.         void inorder(node *root)
  79.         {
  80.             node *p;
  81.             p = root;
  82.             top = 0;
  83.             do
  84.             {
  85.                 while (p != NULL)
  86.                 {
  87.                     stk[top] = p->data;
  88.                     top++;
  89.                     p = p->left;
  90.                 }
  91.                 if (top > 0)
  92.                 {
  93.                     p = pop(root);
  94.                     cout << p->data << " ";
  95.                     p = p->right;
  96.                 }
  97.             }
  98.             while (top != 0 || p != NULL);
  99.         }
  100.  
  101.         node * pop(node *p)
  102.         {
  103.             int ch;
  104.             ch = stk[top - 1];
  105.             if (p->data == ch)
  106.             {
  107.                 top--;
  108.                 return p;
  109.             }
  110.             if (p->data > ch)
  111.                 pop(p->left);
  112.             else
  113.                 pop(p->right);
  114.         }
  115. };
  116.  
  117. int main(int argc, char **argv)
  118. {
  119.     tree t1;
  120.     int ch, n, i;
  121.     while (1)
  122.     {
  123.         cout
  124.                 << "\n1.INSERT\n2.DISPLAY\n3.INORDER TRAVERSE\n4.EXIT\nEnter your choice:";
  125.         cin >> ch;
  126.         switch (ch)
  127.         {
  128.             case 1:
  129.                 cout << "enter no of elements to insert:";
  130.                 cin >> n;
  131.                 for (i = 1; i <= n; i++)
  132.                 {
  133.                     cin >> ch;
  134.                     t1.insert(ch);
  135.                 }
  136.                 break;
  137.             case 2:
  138.                 t1.display(t1.root);
  139.                 break;
  140.             case 3:
  141.                 t1.inorder(t1.root);
  142.                 break;
  143.             case 4:
  144.                 exit(1);
  145.         }
  146.     }
  147. }

Output:

advertisement
$ g++ NonRecursiveInorder.cpp
$ a.out
 
1.INSERT
2.DISPLAY
3.INORDER TRAVERSE
4.EXIT
Enter your choice:1
enter no of elements to insert:5
12 23 34 45 56
 
1.INSERT
2.DISPLAY
3.INORDER TRAVERSE
4.EXIT
Enter your choice:3
12 23 34 45 56 
 
1.INSERT
2.DISPLAY
3.INORDER TRAVERSE
4.EXIT
Enter your choice:4
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.