Traversal In Binary Tree :
Preorder traversal (NLR) :
- Visit the root(N)
- Traverse the left subtree of root in preorder(L)
- Traverse the right subtree of root in preorder(R)
Inorder Traversal (LNR) :
- Traverse the left subtree of root in inorder(L)
- Visit the root(N)
- Traverse the right subtree of root in inorder(R)
Postorder Traversal (LRN) :
- Traverse the left subtree of root in postorder(L)
- Traverse the right subtree of root in postorder(R)
- Visit the root(N)
Algorithm for preorder(*ptr):
STEP 1: START
STEP 2: IF(ptr == NULL ) then RETURN
STEP 3: Then PRINT("%d ",ptrinfo)
STEP 4: Then call preorder(ptrlchild)
STEP 5: Then call preorder(ptrrchild)
STEP 6: STOP.
Algorithm for inorder(*ptr):
STEP 1: START
STEP 2: IF(ptr = NULL ) then RETURN
STEP 3: Then call inorder(ptrlchild)
STEP 4: Then PRINT("%d ",ptrinfo)
STEP 5: Then call inorder(ptrrchild)
STEP 6: STOP.
Algorithm for postorder(*ptr):
STEP 1: START
STEP 2: IF(ptr = NULL ) then RETURN
STEP 3: Then call postorder(ptrlchild)
STEP 4: Then call postorder(ptrrchild) S
TEP 5: Then PRINT("%d ",ptrinfo)
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
When you think of a billion-dollar tech company, you probably imagine rooms full of monitors with dashboards and non-stop data streams.
