Note 1

Take Note:

Take a note while surfing.

Note With Ink

Give your Note a Colorful Tag.

Easy to Access

Stay on same information and in Sync wherever you are.

Note 2

Take Note:

Organize your information,It may take Shape.

Think With Ink

Differ your Content by Color.

Easy to Access

Easy to pull up your content from anywhere anytime.

Note 3

Take Note:

Don't Let information to miss,Because it take shape

Note With Ink

Simple an Easy Way to take a note.

Easy to Access

Get the same in next visit.

Please wait...

Program Discussion :: Trees
Home > Programs > Trees

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


#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 */
    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;
        done = 1; 
} /* end of while */
/* 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");
/* 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 */
    printf("Stack Underflow \n");
    top = *top_ref;
    res = top->t;
    *top_ref = top->next;
    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;

/* Driver program to test above functions*/
int main()

/* Constructed binary tree is
        / \
           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); 


return 0;

Asked In ::

Post Your Answer Here:

Name *


Post Your Reply Here: