C++ Program For Inorder Tree Traversal without Recursion

This C++ program, without recursion, displays the nodes of a particular binary tree in 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.

```
/*
```

 * C++ Program For Inorder Tree Traversal without recursion

```
 */
```
```
#include<iostream>
```
```
using namespace std;
```
```
#include<conio.h>
```
```
struct tree
```
```
{
```
```
    tree *l, *r;
```
```
    int data;
```
```
}*root = NULL, *p = NULL, *s = NULL;
```
```
struct node
```
```
{
```
```
    tree *pt;
```
```
    node *next;
```

}*q = NULL, *top = NULL, *np = NULL;

```
void create()
```
```
{
```
```
    int value ,c = 0;      
```
```
    while (c < 6)
```
```
    {
```
```
        if (root == NULL)
```
```
        {
```
```
            root = new tree;
```

            cout<<"enter value of root node\n";

```
            cin>>root->data;
```
```
            root->r = NULL;
```
```
            root->l = NULL;
```
```
        }
```
```
        else
```
```
        {
```
```
            p = root;
```

            cout<<"enter value of node\n";

```
            cin>>value;
```
```
            while(true)
```
```
            {
```
```
                if(value < p->data)
```
```
                {
```
```
                    if (p->l == NULL)
```
```
                    {
```

                        p->l = new tree;

```
                        p = p->l;
```

                        p->data = value;

```
                        p->l = NULL;
```
```
                        p->r = NULL;
```

                        cout<<"value entered in left\n";

```
                        break;
```
```
                    }
```

                    else if (p->l != NULL)

```
                    {
```
```
                        p = p->l;
```
```
                    }
```
```
                }
```

               else if (value > p->data)

```
               {
```
```
                    if (p->r == NULL)
```
```
                    {
```

                        p->r = new tree;

```
                        p = p->r;
```

                        p->data = value;

```
                        p->l = NULL;
```
```
                        p->r = NULL;
```

                        cout<<"value entered in right\n";

```
                        break;
```
```
                    }
```

                    else if(p->r != NULL)

```
                    {
```
```
                       p = p->r;
```
```
                    }
```
```
                }
```
```
            }
```
```
        }
```
```
    c++;
```
```
    }
```
```
}
```
```
void push(tree *ptr)
```
```
{
```
```
    np = new node;
```
```
    np->pt = ptr;
```
```
    np->next = NULL;
```
```
    if (top == NULL)
```
```
    {
```
```
        top = np;
```
```
    }
```
```
    else
```
```
    {
```
```
        q = top;
```
```
        top = np;
```
```
        np->next = q;
```
```
    }
```
```
}
```
```
tree *pop()
```
```
{
```
```
    if (top == NULL)
```
```
    {
```
```
        cout<<"underflow\n";
```
```
    }
```
```
    else
```
```
    {
```
```
        q = top;
```
```
        top = top->next;
```
```
        return(q->pt);
```
```
        delete(q);
```
```
    }
```
```
}
```
```
void traverse(tree *p)
```
```
{
```
```
    push(p);
```
```
    while (top != NULL)
```
```
    {
```
```
        while (p != NULL)
```
```
        {
```
```
            push(p);
```
```
            p = p->l;
```
```
        }
```
```
        if (top != NULL && p == NULL)
```
```
        {
```
```
            p = pop();
```
```
            cout<<p->data<<endl;
```
```
            p = p->r;
```
```
        }
```
```
    }
```
```
}
```
```
int main()
```
```
{
```
```
    int val;
```
```
    create();
```

    cout<<"printing traversal in inorder\n";

```
    traverse(root);                 
```
```
    getch();
```
```
}
```

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

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

If you wish to look at all C++ Programming examples, go to C++ Programs.

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 Implement Dijkstra’s Algorithm using Priority_queue(Heap)

» Next - C++ Program to Find Transitive Closure of a Graph

Recommended Posts: