# 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. `}`

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
```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:

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, 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 no of elements to insert:5
12 23 34 45 56

1.INSERT
2.DISPLAY
3.INORDER TRAVERSE
4.EXIT
12 23 34 45 56

1.INSERT
2.DISPLAY
3.INORDER TRAVERSE
4.EXIT

------------------
(program exited with code: 0)

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