Monday, August 20, 2012

Preorder traversal of a BST, iteratively using a Stack


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

#define MAX 100

typedef struct node{
 int data;
 struct node* left;
 struct node* right;
}Node;

Node* s[MAX];
int top = -1;

Node* newNode(int data){
 Node* n = (Node *)malloc(sizeof(Node));
 n->data = data;
 n->left = NULL;
 n->right = NULL;
 return n;
}

void insertNode(Node* root,int data){
 if(data < root->data){
  if(root->left == NULL){
   root->left = newNode(data);
  } else {
   insertNode(root->left,data);
  }
 } else {
  if(root->right == NULL){
   root->right = newNode(data);
  } else {
   insertNode(root->right,data);
  }
 }
}

Node* createBST(Node **rootRef){
 Node *root = newNode(4);
 insertNode(root,2);
 insertNode(root,1);
 insertNode(root,3);
 insertNode(root,6);
 insertNode(root,5);
 insertNode(root,7);
 *rootRef = root;
}

void push(Node* n){
s[++top] = n;
}

Node* pop(){
return s[top--];
}

int isempty(){
return (top==-1);
}

void preorder(Node* root){
if(root == NULL){
return;
}
push(root);
while(!isempty()){
Node *temp = pop();
printf("%d ",temp->data);
if(temp->right != NULL){
push(temp->right);
}
if(temp->left != NULL){
push(temp->left);
}
}
}

int main(){
 Node* root = NULL;
 createBST(&root);

 printf("\nPREORDER :\n");
 preorder(root);

 return 0;
}

No comments:

Post a Comment