Inorder Tree Traversal without using Recursion in C++

In a binary search tree, the inorder traversal method follows the Left Node Right or Left Root Right policy. In the in-order traversal algorithm, the subtree on the left side of the root node, then the root, and then the subtree on the right side of the root node is traversed.

Method 1:

This C++ program, without recursion, displays the nodes of a particular binary tree in an inorder fashion without using recursive traversal.

Here is the source code of the C++ program to display the tree in inorder. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

  1. /*
  2.  * C++ Program For Inorder Tree Traversal without recursion
  3.  */
  4. #include<iostream>
  5. using namespace std;
  6. #include<conio.h>
  7. struct tree
  8. {
  9.     tree *l, *r;
  10.     int data;
  11. }*root = NULL, *p = NULL, *s = NULL;
  12. struct node
  13. {
  14.     tree *pt;
  15.     node *next;
  16. }*q = NULL, *top = NULL, *np = NULL;       
  17. void create()
  18. {
  19.     int value ,c = 0;      
  20.     while (c < 6)
  21.     {
  22.         if (root == NULL)
  23.         {
  24.             root = new tree;
  25.             cout<<"enter value of root node\n";
  26.             cin>>root->data;
  27.             root->r = NULL;
  28.             root->l = NULL;
  29.         }
  30.         else
  31.         {
  32.             p = root;
  33.             cout<<"enter value of node\n";
  34.             cin>>value;
  35.             while(true)
  36.             {
  37.                 if(value < p->data)
  38.                 {
  39.                     if (p->l == NULL)
  40.                     {
  41.                         p->l = new tree;
  42.                         p = p->l;
  43.                         p->data = value;
  44.                         p->l = NULL;
  45.                         p->r = NULL;
  46.                         cout<<"value entered in left\n";
  47.                         break;
  48.                     }
  49.                     else if (p->l != NULL)
  50.                     {
  51.                         p = p->l;
  52.                     }
  53.                 }
  54.                else if (value > p->data)
  55.                {
  56.                     if (p->r == NULL)
  57.                     {
  58.                         p->r = new tree;
  59.                         p = p->r;
  60.                         p->data = value;
  61.                         p->l = NULL;
  62.                         p->r = NULL;
  63.                         cout<<"value entered in right\n";
  64.                         break;
  65.                     }
  66.                     else if(p->r != NULL)
  67.                     {
  68.                        p = p->r;
  69.                     }
  70.                 }
  71.             }
  72.         }
  73.     c++;
  74.     }
  75. }
  76. void push(tree *ptr)
  77. {
  78.     np = new node;
  79.     np->pt = ptr;
  80.     np->next = NULL;
  81.     if (top == NULL)
  82.     {
  83.         top = np;
  84.     }
  85.     else
  86.     {
  87.         q = top;
  88.         top = np;
  89.         np->next = q;
  90.     }
  91. }
  92. tree *pop()
  93. {
  94.     if (top == NULL)
  95.     {
  96.         cout<<"underflow\n";
  97.     }
  98.     else
  99.     {
  100.         q = top;
  101.         top = top->next;
  102.         return(q->pt);
  103.         delete(q);
  104.     }
  105. }
  106. void traverse(tree *p)
  107. {
  108.     push(p);
  109.     while (top != NULL)
  110.     {
  111.         while (p != NULL)
  112.         {
  113.             push(p);
  114.             p = p->l;
  115.         }
  116.         if (top != NULL && p == NULL)
  117.         {
  118.             p = pop();
  119.             cout<<p->data<<endl;
  120.             p = p->r;
  121.         }
  122.     }
  123. }
  124. int main()
  125. {
  126.     int val;
  127.     create();
  128.     cout<<"printing traversal in inorder\n";
  129.     traverse(root);                 
  130.     getch();
  131. }

advertisement
advertisement
Output
enter value of root node
6
enter value of node
2
value entered in left
enter value of node
9
value entered in right
enter value of node
3
value entered in right
enter value of node
5
value entered in right
enter value of node
7
value entered in left
printing traversal in inorder
2
3
5
6
7
9
6

Method 2:

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
Here is the source code of the C++ Program to Perform Inorder Traversal of a Given Binary Tree without using recursion.
  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:

$ 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
If you wish to look at all C++ Programming examples, go to C++ Programs.

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 & discussions at Telegram SanfoundryClasses.