Iterative inorder traversal

[gaurav_13191]

Hi all, I am trying to code iterative implementation of bst. But I am encountering some problems as the stack is not updated as it should be. I am getting incorrect output.Some suggestions would be welcomed.

/*Operations to be performed:-
->Insertion
->Deletion
->Modification
->Search
->Minimum
->Maximum
->Predecessor
->Successor
->Inorder tree walk
->Preorder tree walk
->Postorder tree walk
NOTE- Iterative program
*/

#include<stdio.h>
#include<stdlib.h>

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

struct stack
{
   int top;
   struct bst *arr[100];
};

void initialize(struct stack *);
void push(struct stack *,struct bst *);
struct bst *pop(struct stack *);
struct bst *insert(struct bst *,int);
/*struct bst *deletion(struct bst *,int);
struct bst *update(struct bst *,int);
void search(struct bst *,int);
int minimum(struct bst *);
int maximum(struct bst *);
struct bst *predecessor(struct bst *,int);
struct bst *successor(struct bst *,int);
*/
void inorder(struct bst *);
/*void preorder(struct bst *);
void postorder(struct bst *);
void display(struct stack *s);
*/

int main()
{
  //int n,i=0;
  struct bst *root=NULL;
  //struct stack *q=(struct stack *)malloc(sizeof(struct stack));
  //initialize(q);
  //printf("Enter number of nodes:");
  //scanf("%d",&n);
  root=insert(root,5);
  //printf("%d",root->data);
  root=insert(root,15);
  root=insert(root,10);
  root=insert(root,8);
  root=insert(root,13);
  root=insert(root,3);
  root=insert(root,4);

  inorder(root);
  return 0;
}

void initialize(struct stack *s)
{
    int i=0;
    s->top=-1;
    while(i++<100)
     s->arr[i]=NULL;
}

void push(struct stack *s,struct bst *q)
{
    if(s->top==99)
    {
        printf("Stack full");
        return;
    }
    else
    {
        s->top++;
        s->arr[s->top]=q;
    }
}

struct bst *pop(struct stack *s)
{
    struct bst *ptr=NULL;
    if(s->top==-1)
     printf("\nStack empty");
    else
     ptr=s->arr[(s->top)--];
    //printf("%d",ptr->data);
    return ptr;
}


struct bst *insert(struct bst *root,int val)
{
    int flag=0;
    struct bst *save,*ptr,*temp;
    temp=(struct bst *)malloc(sizeof(struct bst));
    if(temp==NULL)
     return NULL;
    else
     temp->data=val;

    if(root==NULL)
    {
        root=temp;
        temp->left=temp->right=NULL;
        //printf("%d",root->data);
    }
    else
    {
        //printf("test");
        ptr=root;
        while(ptr!=NULL)
        {
            if(val<=ptr->data)
            {
                save=ptr;
                ptr=ptr->left;
                flag=0;
            }
            else
            {
                save=ptr;
                ptr=ptr->right;
                flag=1;
            }
        }
        if(flag)
        {
            save->right=temp;
            temp->left=temp->right=NULL;
        }
        else if(!flag)
        {
            save->left=temp;
            temp->left=temp->right=NULL;
        }
    }
    return root;
}

/*void display(struct stack *s)
{
 int t;
 t=s->top;
 while(t>=0)
 {
     printf("\n%d",s->arr[t--]);
 }
}
*/

void inorder(struct bst *root)
{
    struct bst *temp;
    struct stack *s=(struct stack *)malloc(sizeof(struct stack));
    initialize(s);
    temp=root;
    //printf("%d",temp->left->data);
    while(1)
    {
        while(temp!=NULL)
        {
         //printf("s");
         push(s,temp);
         temp=temp->left;
         continue;
        }

        if(pop(s)==NULL)
        return;

        temp=pop(s);
        printf("%d\t",temp->data);
        temp=temp->right;
    }
}

[nezachem]

You are calling pop() twice. Replace lines 182-185 with

temp = pop(s);
    if(temp == NULL)
        return;

[gaurav_13191]

Thanks a lot. I did a lot of debugging but was unable to figure out this minor mistake.