# Inorder Traversal of a Binary Tree without using Recursion in C

«
»
This is a C Program to perform inorder traversal. Time Complexity: O(n)

Here is source code of the C Program to Perform Inorder 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<stdio.h>`
2. `#include<stdlib.h>`
3. `#define bool int`
4. ` `
5. `/* A binary tree tNode has data, pointer to left child`
6. ` and a pointer to right child */`
7. `struct tNode {`
8. `    int data;`
9. `    struct tNode* left;`
10. `    struct tNode* right;`
11. `};`
12. ` `
13. `/* Structure of a stack node. Linked List implementation is used for`
14. ` stack. A stack node contains a pointer to tree node and a pointer to`
15. ` next stack node */`
16. `struct sNode {`
17. `    struct tNode *t;`
18. `    struct sNode *next;`
19. `};`
20. ` `
21. `/* Stack related functions */`
22. `void push(struct sNode** top_ref, struct tNode *t);`
23. `struct tNode *pop(struct sNode** top_ref);`
24. `bool isEmpty(struct sNode *top);`
25. ` `
26. `/* Iterative function for inorder tree traversal */`
27. `void inOrder(struct tNode *root) {`
28. `    /* set current to root of binary tree */`
29. `    struct tNode *current = root;`
30. `    struct sNode *s = NULL; /* Initialize stack s */`
31. `    bool done = 0;`
32. ` `
33. `    while (!done) {`
34. `        /* Reach the left most tNode of the current tNode */`
35. `        if (current != NULL) {`
36. `            /* place pointer to a tree node on the stack before traversing`
37. `             the node's left subtree */`
38. `            push(&s, current);`
39. `            current = current->left;`
40. `        }`
41. ` `
42. `        /* backtrack from the empty subtree and visit the tNode`
43. `         at the top of the stack; however, if the stack is empty,`
44. `         you are done */`
45. `        else {`
46. `            if (!isEmpty(s)) {`
47. `                current = pop(&s);`
48. `                printf("%d ", current->data);`
49. ` `
50. `                /* we have visited the node and its left subtree.`
51. `                 Now, it's right subtree's turn */`
52. `                current = current->right;`
53. `            } else`
54. `                done = 1;`
55. `        }`
56. `    } /* end of while */`
57. `}`
58. ` `
59. `/* UTILITY FUNCTIONS */`
60. `/* Function to push an item to sNode*/`
61. `void push(struct sNode** top_ref, struct tNode *t) {`
62. `    /* allocate tNode */`
63. `    struct sNode* new_tNode = (struct sNode*) malloc(sizeof(struct sNode));`
64. ` `
65. `    if (new_tNode == NULL) {`
66. `        printf("Stack Overflow \n");`
67. `        getchar();`
68. `        exit(0);`
69. `    }`
70. ` `
71. `    /* put in the data  */`
72. `    new_tNode->t = t;`
73. ` `
74. `    /* link the old list off the new tNode */`
75. `    new_tNode->next = (*top_ref);`
76. ` `
77. `    /* move the head to point to the new tNode */`
78. `    (*top_ref) = new_tNode;`
79. `}`
80. ` `
81. `/* The function returns true if stack is empty, otherwise false */bool isEmpty(`
82. `        struct sNode *top) {`
83. `    return (top == NULL) ? 1 : 0;`
84. `}`
85. ` `
86. `/* Function to pop an item from stack*/`
87. `struct tNode *pop(struct sNode** top_ref) {`
88. `    struct tNode *res;`
89. `    struct sNode *top;`
90. ` `
91. `    /*If sNode is empty then error */`
92. `    if (isEmpty(*top_ref)) {`
93. `        printf("Stack Underflow \n");`
94. `        getchar();`
95. `        exit(0);`
96. `    } else {`
97. `        top = *top_ref;`
98. `        res = top->t;`
99. `        *top_ref = top->next;`
100. `        free(top);`
101. `        return res;`
102. `    }`
103. `}`
104. ` `
105. `/* Helper function that allocates a new tNode with the`
106. ` given data and NULL left and right pointers. */`
107. `struct tNode* newtNode(int data) {`
108. `    struct tNode* tNode = (struct tNode*) malloc(sizeof(struct tNode));`
109. `    tNode->data = data;`
110. `    tNode->left = NULL;`
111. `    tNode->right = NULL;`
112. ` `
113. `    return (tNode);`
114. `}`
115. ` `
116. `/* Driver program to test above functions*/`
117. `int main() {`
118. ` `
119. `    /* Constructed binary tree is`
120. `       1`
121. `     /   \`
122. `   2      3`
123. `  /  \`
124. `4     5`
125. `     */`
126. `    struct tNode *root = newtNode(1);`
127. `    root->left = newtNode(2);`
128. `    root->right = newtNode(3);`
129. `    root->left->left = newtNode(4);`
130. `    root->left->right = newtNode(5);`
131. ` `
132. `    inOrder(root);`
133. `    return 0;`
134. `}`

Output:

```\$ gcc InorderNonRecursive.c
\$ ./a.out

4 2 5 1 3```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now! 