Inorder, Postorder and Preorder traversal in BST

Snehashish Das 1 Tallied Votes 143 Views Share

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){
        printf("Key not found.....\n");
        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