Inorder Tree Traversal without recursion?

790 views Asked by At

I tried to code Inorder tree traversal without recursion and implementing my own stack as an array.

Code :-

    struct treenode
    {
       struct treenode *left;
       int data;
       struct treenode *right;
    };

    struct stack
    {
       int top;
       unsigned capacity;
       struct treenode **array;
    };


    void push(struct stack *stack,struct treenode *current)
    {
       if(isStackFull(stack))
       {
          printf("Stackoverflow !!");
          return;
       }
       else
       {
          stack->array[++stack->top] = current;
       }
    }

    struct treenode *pop(struct stack *stack)
    {
       if(isStackEmpty(stack))
       {
          printf("Underflow !!");
          exit(0);
       }
       else
       {
          struct treenode *current  = stack->array[stack->top--];
          return current;
       }
    }

    void inorderwithoutRecursion(struct treenode *tree)
    {
       struct stack *stack = createStack(5);
       struct treenode *current = tree;
       int end = 0;

       while(!end)
       {
          if(current != NULL)
          {
             push(stack,current);
             current = current->left;
          }
          else
          {
             if(!isStackEmpty(stack))
             {
                struct treenode *current = pop(stack);
                printf("%d\n",current->data);

                current = current->right;
             }
             else
             {
                end = 1;
             }
          }
       }
    }
struct stack *createStack(unsigned capacity)
{
   struct stack *temp = malloc(sizeof(struct stack));
   temp->top = -1;
   temp->capacity = capacity;
   temp->array = malloc(sizeof(int *) * temp->capacity);
   return temp;
}

struct treenode *createTree(int value)
{
   struct treenode * temp = malloc(sizeof(struct treenode));
   temp->data = value;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}

int main()
{
   struct treenode *tree = createTree(1);
   tree->right = createTree(2);
   tree->right->left = createTree(3);
   tree->right->left->right = createTree(4);
   tree->right->left->right->left = createTree(5);

   printf("Inorder Traversal without using recursion is: \n");
   inorderwithoutRecursion(tree);
}

I am getting output as :-

Inorder Traversal without using recursion is: 
1

It is not giving complete inorder traversal. Well, it should output 13542, but this gives only one number.

There is no error here, but why is it giving only one number and not others.

Am I missing some details here ?

0

There are 0 answers