Get Off-Campus Placement Jobs Info !!!
Programs asked in Mettl Coding Round
Click To Practce List of Programs asked in Nagarro !!!

# Program Discussion :: Trees

Home > Programs > Trees

48 / 17

## Write a program to traverse the tree in inorder without using recursion

``````
#include#include#define bool int/* A binary tree tNode has data, pointer to left childand 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 thegiven 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);getchar();return 0;}
``````

• Rate This: +1 -0 +
• To Reading List 