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.

```
#include<stdio.h>
```
```
#include<stdlib.h>
```
```
#define bool int
```
```
 
```

/* A binary tree tNode has data, pointer to left child

```
 and a pointer to right child */
```
```
struct tNode {
```
```
    int data;
```
```
    struct tNode* left;
```
```
    struct tNode* right;
```
```
};
```
```
 
```

/* Structure of a stack node. Linked List implementation is used for

 stack. A stack node contains a pointer to tree node and a pointer to

```
 next stack node */
```
```
struct sNode {
```
```
    struct tNode *t;
```
```
    struct sNode *next;
```
```
};
```
```
 
```
```
/* Stack related functions */
```

void push(struct sNode** top_ref, struct tNode *t);

struct tNode *pop(struct sNode** top_ref);

```
bool isEmpty(struct sNode *top);
```
```
 
```

/* Iterative function for inorder tree traversal */

```
void inOrder(struct tNode *root) {
```

    /* set current to root of binary tree */

```
    struct tNode *current = root;
```

    struct sNode *s = NULL; /* Initialize stack s */

```
    bool done = 0;
```
```
 
```
```
    while (!done) {
```

        /* Reach the left most tNode of the current tNode */

```
        if (current != NULL) {
```

            /* place pointer to a tree node on the stack before traversing

             the node's left subtree */

```
            push(&s, current);
```
```
            current = current->left;
```
```
        }
```
```
 
```

        /* backtrack from the empty subtree and visit the tNode

         at the top of the stack; however, if the stack is empty,

```
         you are done */
```
```
        else {
```
```
            if (!isEmpty(s)) {
```
```
                current = pop(&s);
```

                printf("%d ", current->data);

```
 
```

                /* we have visited the node and its left subtree.

                 Now, it's right subtree's turn */

                current = current->right;

```
            } else
```
```
                done = 1;
```
```
        }
```
```
    } /* end of while */
```
```
}
```
```
 
```
```
/* UTILITY FUNCTIONS */
```
```
/* Function to push an item to sNode*/
```

void push(struct sNode** top_ref, struct tNode *t) {

```
    /* allocate tNode */
```

    struct sNode* new_tNode = (struct sNode*) malloc(sizeof(struct sNode));

```
 
```
```
    if (new_tNode == NULL) {
```
```
        printf("Stack Overflow \n");
```
```
        getchar();
```
```
        exit(0);
```
```
    }
```
```
 
```
```
    /* put in the data  */
```
```
    new_tNode->t = t;
```
```
 
```

    /* link the old list off the new tNode */

```
    new_tNode->next = (*top_ref);
```
```
 
```

    /* move the head to point to the new tNode */

```
    (*top_ref) = new_tNode;
```
```
}
```
```
 
```

/* The function returns true if stack is empty, otherwise false */bool isEmpty(

```
        struct sNode *top) {
```
```
    return (top == NULL) ? 1 : 0;
```
```
}
```
```
 
```
```
/* Function to pop an item from stack*/
```

struct tNode *pop(struct sNode** top_ref) {

```
    struct tNode *res;
```
```
    struct sNode *top;
```
```
 
```
```
    /*If sNode is empty then error */
```
```
    if (isEmpty(*top_ref)) {
```
```
        printf("Stack Underflow \n");
```
```
        getchar();
```
```
        exit(0);
```
```
    } else {
```
```
        top = *top_ref;
```
```
        res = top->t;
```
```
        *top_ref = top->next;
```
```
        free(top);
```
```
        return res;
```
```
    }
```
```
}
```
```
 
```

/* Helper function that allocates a new tNode with the

 given data and NULL left and right pointers. */

```
struct tNode* newtNode(int data) {
```

    struct tNode* tNode = (struct tNode*) malloc(sizeof(struct tNode));

```
    tNode->data = data;
```
```
    tNode->left = NULL;
```
```
    tNode->right = NULL;
```
```
 
```
```
    return (tNode);
```
```
}
```
```
 
```

/* Driver program to test above functions*/

```
int main() {
```
```
 
```
```
    /* Constructed binary tree is
```
```
       1
```
```
     /   \
```
```
   2      3
```
```
  /  \
```
```
4     5
```
```
     */
```
```
    struct tNode *root = newtNode(1);
```
```
    root->left = newtNode(2);
```
```
    root->right = newtNode(3);
```
```
    root->left->left = newtNode(4);
```
```
    root->left->right = newtNode(5);
```
```
 
```
```
    inOrder(root);
```
```
    return 0;
```
```
}
```

Output:

$ gcc InorderNonRecursive.c
$ ./a.out
 
4 2 5 1 3

Sanfoundry Global Education & Learning Series – 1000 C Programs.

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

« Prev - C Program to Check the Connectivity of Graph Using DFS

» Next - C Program to Generate Random Partition from Given Set

Related Posts:

Recommended Articles: