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.

```
/*
```

 * 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

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.

```
#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 inorder(node *root)
```
```
        {
```
```
            node *p;
```
```
            p = root;
```
```
            top = 0;
```
```
            do
```
```
            {
```
```
                while (p != NULL)
```
```
                {
```
```
                    stk[top] = p->data;
```
```
                    top++;
```
```
                    p = p->left;
```
```
                }
```
```
                if (top > 0)
```
```
                {
```
```
                    p = pop(root);
```

                    cout << p->data << " ";

```
                    p = p->right;
```
```
                }
```
```
            }
```

            while (top != 0 || p != NULL);

```
        }
```
```
 
```
```
        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.INORDER 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.inorder(t1.root);
```
```
                break;
```
```
            case 4:
```
```
                exit(1);
```
```
        }
```
```
    }
```
```
}
```

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.

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

« Prev - C++ Program to Implement Dijkstra’s Algorithm using Priority Queue

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

Related Posts:

Recommended Articles: