Postorder Traversal of a Binary Tree without using Recursion in C++

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

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

Output:

$ g++ NonRecursivePostorder.cpp
$ a.out
 
 
1.INSERT
2.DISPLAY
3.POSTORDER TRAVERSE
4.EXIT
Enter your choice:1
Enter no of elements to insert: 5
12 23 34 45 56
 
1.INSERT
2.DISPLAY
3.POSTORDER TRAVERSE
4.EXIT
Enter your choice:3
56 45 34 23 12 
 
1.INSERT
2.DISPLAY
3.POSTORDER 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 & discussions at Telegram SanfoundryClasses.