# Inorder, Postorder and Preorder traversal in BST

## Traversal In Binary Tree :

Preorder traversal (NLR) :

1. Visit the root(N)
2. Traverse the left subtree of root in preorder(L)
3. Traverse the right subtree of root in preorder(R)

Inorder Traversal (LNR) :

1. Traverse the left subtree of root in inorder(L)
2. Visit the root(N)
3. Traverse the right subtree of root in inorder(R)

Postorder Traversal (LRN) :

1. Traverse the left subtree of root in postorder(L)
2. Traverse the right subtree of root in postorder(R)
3. Visit the root(N)

Algorithm for preorder(*ptr):
STEP 1: START
STEP 2: IF(ptr == NULL ) then RETURN
STEP 3: Then PRINT("%d ",ptrinfo)
STEP 4: Then call preorder(ptrlchild)
STEP 5: Then call preorder(ptrrchild)
STEP 6: STOP.

Algorithm for inorder(*ptr):
STEP 1: START
STEP 2: IF(ptr = NULL ) then RETURN
STEP 3: Then call inorder(ptrlchild)
STEP 4: Then PRINT("%d ",ptrinfo)
STEP 5: Then call inorder(ptrrchild)
STEP 6: STOP.

Algorithm for postorder(*ptr):
STEP 1: START
STEP 2: IF(ptr = NULL ) then RETURN
STEP 3: Then call postorder(ptrlchild)
STEP 4: Then call postorder(ptrrchild) S
TEP 5: Then PRINT("%d ",ptrinfo)
STEP 6: STOP.

Code :

``````/*Operations in Binary Search Tree*/
#include<stdio.h>
#include<stdlib.h>
#define MAX 100

struct node
{
struct node *lchild;
int info;
struct node *rchild;
};

struct node *insert(struct node *ptr, int ikey);
void preorder(struct node *ptr);
void inorder(struct node *ptr);
void postorder(struct node *ptr);

void main( )
{
printf(". . . . . . . . BINARY SEARCH TREE . . . . . . . .");
printf("\n");
struct node *root=NULL,*ptr;
int choice,k;
root = insert(root, 50);
root = insert(root, 10);
root = insert(root, 60);
root = insert(root, 40);
root = insert(root, 30);
root = insert(root, 5);
printf("\nPreorder Traversal : \n");
preorder(root);
printf("\nInorder Traversal : \n");
inorder(root);
printf("\nPostorder Traversal : \n");
postorder(root);
}/*End of main( )*/

struct node *insert(struct node *ptr, int ikey )
{
if(ptr==NULL){
ptr = (struct node *) malloc(sizeof(struct node));
ptr->info = ikey;
ptr->lchild = NULL;
ptr->rchild = NULL;}
else if(ikey < ptr->info)   /*Insertion in left subtree*/
ptr->lchild = insert(ptr->lchild, ikey);
else if(ikey > ptr->info)   /*Insertion in right subtree */
ptr->rchild = insert(ptr->rchild, ikey);
else
printf("Duplicate key.....\n");
return ptr;
}/*End of insert( )*/

struct node *del(struct node *ptr, int dkey)
{
struct node *tmp, *succ;
if( ptr == NULL){
return(ptr);}
if( dkey < ptr->info )/*delete from left subtree*/
ptr->lchild = del(ptr->lchild, dkey);
else if( dkey > ptr->info )/*delete from right subtree*/
ptr->rchild = del(ptr->rchild, dkey);
else
{
/*key to be deleted is found*/
if( ptr->lchild!=NULL  &&  ptr->rchild!=NULL )  /*2 children*/
{
succ=ptr->rchild;
while(succ->lchild)
succ=succ->lchild;
ptr->info=succ->info;
ptr->rchild = del(ptr->rchild, succ->info);
}
else
{
tmp = ptr;
if( ptr->lchild != NULL ) /*only left child*/
ptr = ptr->lchild;
else if( ptr->rchild != NULL) /*only right child*/
ptr = ptr->rchild;
else    /* no child */
ptr = NULL;
free(tmp);
}
printf("\nNode deleted...");
}
return ptr;
}/*End of del( )*/
void preorder(struct node *ptr)
{
if(ptr == NULL )    /*Base Case*/
return;
printf("%d  ",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);
}/*End of preorder( )*/

void inorder(struct node *ptr)
{
if(ptr == NULL )/*Base Case*/
return;
inorder(ptr->lchild);
printf("%d  ",ptr->info);
inorder(ptr->rchild);
}/*End of inorder( )*/

void postorder(struct node *ptr)
{
if(ptr == NULL )/*Base Case*/
return;
postorder(ptr->lchild);
postorder(ptr->rchild);
printf("%d  ",ptr->info);

}/*End of postorder( )*/``````

Output :

``````. . . . . . . . BINARY SEARCH TREE . . . . . . . .

Preorder Traversal :
50  10  5  40  30  60
Inorder Traversal :
5  10  30  40  50  60
Postorder Traversal :
5  30  40  10  60  50``````
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.