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

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.

```
#include<iostream>
```
```
#include<conio.h>
```
```
#include<stdlib.h>
```
```
 
```
```
using namespace std;
```
```
 
```
```
class node
```
```
{
```
```
    public:
```
```
        class node *left;
```
```
        class node *right;
```
```
        int data;
```
```
};
```
```
 
```
```
class tree: public node
```
```
{
```
```
    public:
```
```
        int stk[50], top;
```
```
        node *root;
```
```
        tree()
```
```
        {
```
```
            root = NULL;
```
```
            top = 0;
```
```
        }
```
```
        void insert(int ch)
```
```
        {
```
```
            node *temp, *temp1;
```
```
            if (root == NULL)
```
```
            {
```
```
                root = new node;
```
```
                root->data = ch;
```
```
                root->left = NULL;
```
```
                root->right = NULL;
```
```
                return;
```
```
            }
```
```
            temp1 = new node;
```
```
            temp1->data = ch;
```

            temp1->right = temp1->left = NULL;

```
            temp = search(root, ch);
```
```
            if (temp->data > ch)
```
```
                temp->left = temp1;
```
```
            else
```
```
                temp->right = temp1;
```
```
 
```
```
        }
```

        node *search(node *temp, int ch)

```
        {
```
```
            if (root == NULL)
```
```
            {
```

                cout << "no node present";

```
                return NULL;
```
```
            }
```

            if (temp->left == NULL && temp->right == NULL)

```
                return temp;
```
```
 
```
```
            if (temp->data > ch)
```
```
            {
```
```
                if (temp->left == NULL)
```
```
                    return temp;
```
```
                search(temp->left, ch);
```
```
            }
```
```
            else
```
```
            {
```

                if (temp->right == NULL)

```
                    return temp;
```

                search(temp->right, ch);

```
 
```
```
            }
```
```
        }
```
```
 
```
```
        void display(node *temp)
```
```
        {
```
```
            if (temp == NULL)
```
```
                return;
```
```
            display(temp->left);
```
```
            cout << temp->data << " ";
```
```
            display(temp->right);
```
```
        }
```
```
        void postorder(node *root)
```
```
        {
```
```
            node *p;
```
```
            p = root;
```
```
            top = 0;
```
```
 
```
```
            while (1)
```
```
            {
```
```
                while (p != NULL)
```
```
                {
```
```
                    stk[top] = p->data;
```
```
                    top++;
```

                    if (p->right != NULL)

                        stk[top++] = -p->right->data;

```
                    p = p->left;
```
```
                }
```

                while (stk[top - 1] > 0 || top == 0)

```
                {
```
```
                    if (top == 0)
```
```
                        return;
```

                    cout << stk[top - 1] << " ";

```
                    p = pop(root);
```
```
                }
```
```
                if (stk[top - 1] < 0)
```
```
                {
```

                    stk[top - 1] = -stk[top - 1];

```
                    p = pop(root);
```
```
                }
```
```
            }
```
```
 
```
```
        }
```
```
        node * pop(node *p)
```
```
        {
```
```
            int ch;
```
```
            ch = stk[top - 1];
```
```
            if (p->data == ch)
```
```
            {
```
```
                top--;
```
```
                return p;
```
```
            }
```
```
            if (p->data > ch)
```
```
                pop(p->left);
```
```
            else
```
```
                pop(p->right);
```
```
        }
```
```
};
```
```
 
```
```
int main(int argc, char **argv)
```
```
{
```
```
    tree t1;
```
```
    int ch, n, i;
```
```
    while (1)
```
```
    {
```
```
        cout
```

                << "\n1.INSERT\n2.DISPLAY\n3.POSTORDER TRAVERSE\n4.EXIT\nEnter your choice:";

```
        cin >> ch;
```
```
        switch (ch)
```
```
        {
```
```
            case 1:
```

                cout << "Enter no of elements to insert: ";

```
                cin >> n;
```

                for (i = 1; i <= n; i++)

```
                {
```
```
                    cin >> ch;
```
```
                    t1.insert(ch);
```
```
                }
```
```
                break;
```
```
            case 2:
```
```
                t1.display(t1.root);
```
```
                break;
```
```
            case 3:
```
```
                t1.postorder(t1.root);
```
```
                break;
```
```
            case 4:
```
```
                exit(1);
```
```
        }
```
```
    }
```
```
}
```

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.

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

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!

« Prev - C++ Program to Perform Preorder Non-Recursive Traversal of a Given Binary Tree

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

Recommended Posts: