Binary Search Tree

A Binary Search Tree is a Binary Tree which satisfies the following conditions:

The left subtree of the root contains keys smaller than the root.
The right subtree of the root contains keys greater than the root.
The left and right subtrees are also Binary Search Trees.
There are no duplicates in the tree.

A Binary Search Tree may be represented using arrays and linked list.

Representation of Binary Search Tree using Arrays:

Array representation of Binary Search Tree requires numbering of all the nodes of the tree beginning from the root to bottom and left to right for the same level. Even the empty nodes are numbered. They are then inserted in the array based on their numbering.

Array contains elements in proper numbering as indicated in the above figure. Null values are left blank in the array or may be filled with zeroes. The required size of the array for n elements will be 2ⁿ-1.

Representation of Binary Search Tree using Linked List:

Linked list representation of a binary tree is using a node that contains three parts, an information part, an address to the left child node and another address to the right child node. A Binary search tree using linked list is explained in the figure below:

Example:

Program to create a Binary Search Tree

Operations: The operations that can be performed on a BST are given below:

Recursive Traversal: (Inorder, Preorder, Postorder)

In-order:

Traverse left subtree.
Visit the root.
Traverse right subtree.

/*Traverses BST in inorder by recursive definition*/
void inorder(BST *root)
{
if(root)
{inorder(root->left);
printf(“%dt”,root->info);
inorder(root->right);
}
}

Pre-order:

Visit the root.
Traverse left subtree.
Traverse right subtree.

/*Traverses BST in preorder by recursive definition*/
void preorder(BST *root)
{
if(root)
{printf(“%dt”,root->info);
preorder(root->left);
preorder(root->right);
}
}

Post-order:

Traverse left subtree.
Traverse right subtree.
Visit the root.

/*Traverses BST in postorder using recursive definition*/
void postorder(BST *root)
{
if(root)
{postorder(root->left);
postorder(root->right);
printf(“%dt”,root->info);
}
}

Non-Recursive Traversal:

/*Global stack declaration used for iterative traversals*/

typedef struct stack
{int top;
BST *items[MAX];
}stk;

/*Checks whether the stack is empty or not*/

int empty(stk *s)
{return(s->top==-1);
}

/*Push a node of BST into the stack*/

void push(stk *s, BST *t)
{if(s->top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
s->items[++(s->top)]=t;
}

/*Pops/returns a node of BST from the top of the stack*/

BST *pop(stk *s)
{if(s->top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
return(s->items[(s->top)–]);
}

Iterative In-order traversal:

/*Iterative Inorder Traversal*/

void iterativeinorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{while(p!=NULL)
{push(&s,p);
p=p->left;
}

if(!empty(&s))
{p=pop(&s);
printf(“%dt”,p->info);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

Iterative Pre-order traversal:

/*Iterative Preorder Traversal*/

void iterativepreorder(BST *root)
{stk s;
BST *p=root;
s.top=-1;
do
{
while(p!=NULL)
{printf(“%dt”,p->info);
push(&s,p);
p=p->left;
}

if(!empty(&s))
{p=pop(&s);
p=p->right;
}
}while(!empty(&s) || p!=NULL);
}

Iterative Post-order traversal:

/*Global stack declarations used for postorder iterative traversals*/
struct pstack
{BST *tree;
int visitedleft,visitedright;
}pstk[MAX];/*Global declaration of top*/
int top=-1;void ppush(struct pstack pstk[],BST *t,int VL,int VR)
{if(top==MAX-1)
{printf(“nStack Overflow…!”);
return;
}
top++;
pstk[top].tree = t;
pstk[top].visitedleft=VL;
pstk[top].visitedright=VR;
}/*Pop the topmost element from the stack*/
struct pstack *ppop(struct pstack *pstk)
{struct pstack *temp;
if(top==-1)
{printf(“nStack Underflow…!”);
return NULL;
}
temp=&pstk[top];
top–;
return temp;
}/*Checks & returns the value of top*/
int pempty()
{return(top==-1);
}/*Iterative Postorder Traversal*/
void iterativepostorder(BST *root)
{
struct pstack *temp;
BST *p=root;
while(1)
{while(p!=NULL)
{ppush(pstk,p,1,0);
p=p->left;
}
if(pempty())
return;
temp=ppop(pstk);
if(temp->visitedleft==1 && temp->visitedright==1)
printf(“%dt”,temp->tree->info);
else
{ppush(pstk,temp->tree,temp->visitedleft,1);
p=temp->tree->right;
}
}
}

Recursive Insertion:

/*Inserts a new node in a BST using recursive definition*/
BST *insert(BST *root,BST *num)
{if(root==NULL)
{root=num;
return root;
}
if(num->info < root->info)
root->left=insert(root->left,num);
else if(num->info > root->info)
root->right=insert(root->right,num);
else
printf(“nDuplicate Value…!”);
return root;
}

Non-Recursive Insertion:

/*Iteratively inserts a newnode in a BST*/
BST *iterativeinsert(BST *root,BST *newnode)
{BST *p=root;
if(root==NULL)
{root=newnode;
return root;
}
while(p!=NULL)
{
if(newnode->info < root->info)
{if(p->left)
p=p->left;
else
{p->left=newnode;
break;
}
}
else if(newnode->info > p->info)
{if(p->right)
p=p->right;
else
{p->right=newnode;
break;
}
}
else
{printf(“nDuplicate key found…!”);
break;
}
}
return root;
}

Finding height:

/*Return height of a tree – recursive definition*/
void heightTree(BST *root,int *height)
{int leftsubtree,rightsubtree;
if(root==NULL)
{*height=0;
}
else
{heightTree(root->left,&leftsubtree);
heightTree(root->right,&rightsubtree);
if(leftsubtree>rightsubtree)
*height=leftsubtree + 1;
else
*height=rightsubtree + 1;
}
}

Finding degree of a given node:

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

Finding total number of nodes:

/*Return total nodes of a BST*/
int totalnodes(BST *root)
{if(root==NULL)
return 0;
else
return(totalnodes(root->left)+totalnodes(root->right)+1);
}

Finding number of leaves/exterior nodes

/*Return external/leaf nodes of a BST*/
int external(BST *root)
{if(root==NULL)
return 0;
else if(root->left==NULL && root->right==NULL)
return 1;
else
return(external(root->left)+external(root->right));
}

Finding number of interior/internal nodes

/*Return internal/interior nodes of a BST*/
int internal(BST *root)
{if((root==NULL) ||
((root->left==NULL)&&(root->right==NULL)))
return 0;
else
return(internal(root->left)+internal(root->right)+1);
}

Determining mirror image:

/*Generating mirror image*/
void mirror(BST *root)
{BST *temp;
if(root)
{mirror(root->left);
mirror(root->right);
temp=root->left;
root->left=root->right;
root->right=temp;
}
}

Finding smallest – Recursive definition

/*Return smallest value from BST using recursive definition*/
int smallestrecursive(BST *root)
{if(root==NULL)
return -1;
if(root->left==NULL)
return(root->info);
else
return smallestrecursive(root->left);
}

Finding smallest – Non-Recursive definition

/*Return smallest value from BST-Iterative Definition*/
int smallest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->left!=NULL)
p=p->left;
return(p->info);
}

Finding largest – Recursive definition

/*Return largest value from BST using recursive definition*/
int largestrecursive(BST *root)
{if(root==NULL)
return -1;
if(root->right==NULL)
return(root->info);
else
return largestrecursive(root->right);
}

Finding largest – Non-Recursive definition

/*Return largest value from BST-Iterative Definition*/
int largest(BST *root)
{BST *p=root;
if(root==NULL)
return -1;
while(p->right!=NULL)
p=p->right;
return(p->info);
}

Recursive Searching:

/*Searching a given node in a BST using recursive definition*/
void searchTree(BST *root,int num)
{if(root==NULL)
{printf(“Number not found…!”);
return;
}
if(num<root->info)
searchTree(root->left,num);
else if(num>root->info)
searchTree(root->right,num);
else
{printf(“nNumber is found…!”);
return;
}
}

Non-Recursive Searching:

/*Searching a given node in a BST using Iterative definition*/
void iterativeSearchTree(BST *root,int num)
{BST *p=root;
if(root==NULL)
{printf(“nNumber not found…!”);
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
{printf(“nNumber not found…!”);
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
{printf(“nNumber not found…!”);
return;
}
}
else
{printf(“nNumber found…!”);
return;
}
}
return;
}

Recursive Deletion:

/*Deletion of a node from BST using recursive definition*/
BST *deletenode(BST *root,int val)
{BST *temp;
if(root==NULL)
return root;
if(val<root->info)
root->left=deletenode(root->left,val);
else if(val>root->info)
root->right=deletenode(root->right,val);
else /*if only one node exists*/
{if(degree(root)==0)
{free(root);
return NULL;
}
/*if node contains one child either left or right*/
if(degree(root)==1)
{
if(root->right)
{temp=root->right;
free(root);
return temp;
}
else
{temp=root->left;
free(root);
return temp;
}
}
/*If node to be deleted contains both
left as well as right child*/
if(degree(root)==2)
{temp=root->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=root->left;
temp=root->right;
free(root);
return temp;
}
}
return root;
}

Function to return degree of a given node:

/*Returns degree of a given node*/
int degree(BST *root)
{if(root->left==NULL && root->right==NULL)
return 0;
else if(root->left!=NULL && root->right!=NULL)
return 2;
else
return 1;
}

Non-Recursive Deletion:

/*Deletion of a node from BST using iterative definition*/
BST *deletenodeiterative(BST *root,int val)
{
BST *cur,*prev,*temp;
if(root==NULL)
return root;
cur=root;
prev=NULL;
while(cur!=NULL && cur->info!=val)
{prev=cur;
if(val<cur->info)
cur=cur->left;
else
cur=cur->right;
}
if(cur==NULL)
return root;
if(degree(cur)==0)
{
if(prev) /*not a root node*/
{
if(prev->left==cur)
prev->left=NULL;
else
prev->right=NULL;
free(cur);
}
else
{free(cur);
return NULL;
}
}
else if(degree(cur)==1)
{if(cur->left)
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->left;
else
prev->right=cur->left;
free(cur);
}
else{
prev=cur->left;
free(cur);
return(prev);
}
}
else
{
if(prev)
{
if(prev->left==cur)
prev->left=cur->right;
else
prev->right=cur->right;
free(cur);
}
else
{
prev=cur->right;
free(cur);
return (prev);
}
}
}
else if(degree(cur)==2)
{if(prev->left==cur)/*case I*/
/*then traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
prev->left=cur->right;
free(cur);
}
else/*case II*/
/*traverse left of right child*/
{temp=cur->right;
while(temp->left!=NULL)
temp=temp->left;
temp->left=cur->left;
if(prev!=NULL)
prev->right=cur->right;
temp=cur->right;
free(cur);
return temp;
}
}
return root;
}

Dispose BST:

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL && left!=NULL && right!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

Level by Level Traversal:

Level by Level traversal or Breadth-First Traversal is a traversal technique in which each node starting from the highest level is visited level by level, such that the nodes for the same level are visited from left to right. An example of Breadth First Traversal or Level by Level traversal is given below:

BFS traversal: A, B, C, D, E, F, G

For its implementation a queue may be used such that after a node is visided, its left or right child nodes, if present, are placed at the rear end of queue and the node at the front of the queue is visited. The ‘C’ function to implement BFS traversal is given below:

/*Queue definition for Breadth first traversal*/

typedef struct queue
{int front,rear;
BST *arr[MAX];
}queue;

void enqueue(queue *q,BST *node)
{if(q->rear==MAX-1)
{printf(“nQueue Overflow…!”);
return;
}
q->arr[++q->rear]=node;
}

BST *dequeue(queue *q)
{if(q->rear==-1)
{printf(“nQueue underflow.”);
return NULL;
}
return(q->arr[q->front++]);
}

int empty(queue *q)
{return (q->front>q->rear);
}

/*Level by Level traversal or Depth First Traversal*/
void levelbyleveltraversal(BST *root)
{
queue q;
q.front=0;
q.rear=-1;
if(root!=NULL)
{enqueue(&q,root);
while(!empty(&q))
{
root=dequeue(&q);
printf(“%dt”,root->info);
if(root->left!=NULL)
enqueue(&q,root->left);
if(root->right!=NULL)
enqueue(&q,root->right);
}
}
}

Disposing:

/*function to dispose the BST*/
BST *dispose(BST *root)
{BST *left,*right;
if(root!=NULL)
{left=root->left;
right=root->right;
free(root);
root=dispose(left);
root=dispose(right);
}
return root;
}

Creating clone:

/*Creating clone of a given tree*/
BST *newroot=NULL; /*global definition of root of new tree*/

void clone(BST *root)
{
BST *temp;
if(root)
{printf(“nMaking node %d”,root->info);
temp=makenode(root->info);
newroot=insert(newroot,temp);
clone(root->left);
clone(root->right);
}
}

Post Views: 1,425