## Binary Search Tree

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

1. The left subtree of the root contains keys smaller than the root.
2. The right subtree of the root contains keys greater than the root.
3. The left and right subtrees are also Binary Search Trees.
4. 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 2n-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: ## 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);
}
}
• 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);
}
}

• 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;
}
/*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:
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)
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)
return;
}
while(p!=NULL)
{if(num<root->info)
{if(root->left)
root=root->left;
else
return;
}
}
else if(num>root->info)
{if(root->right)
root=root->right;
else
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);
}
}

### Definitions:

Red/Black Tree:

It was invented by Rudolf Bayer in 1972.  Red-black trees are one of the preferred methods of maintaining binary search trees.  An n node red-black tree has the height of O(logn).  Moreover balancing time for such a tree on account of insertion and deletion is O(logn).  A red-black tree is a binary search tree with the following properties:

• Every node is colored either red or black.
• The root node is black.
• The value of any node is greater than the value of its left child and less than the value of its right child.
• Every red node that is not a leaf node has only black children.
• Every path from the root to a leaf contains the same number of black nodes.
• All leaf nodes are black.

A red-black tree contains one more field for storing the color the node either red or black.

Splay Tree:

A splay tree is a binary search tree.  It was invented by Daniel Sleator and Robert Tarjan.  All normal operations on a splay tree are based on one basic operation called splaying.  Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree.  To do this, the element is first found with a standard tree search, then tree rotations are performed in a specific fashion to bring the element to the top.  Thus in a splay tree certain elements will be accessed more often than others, thereby, resulting in good performance for certain applications such as implementing caches.  It performs basic operations such as insertion, look-up and removal in O(logn) average time.

Trie:

A trie is a data structure used for storing strings.  One node is reserved for every common prefix.  The strings are stored in extra leaf nodes.

Patricia Tree:

It is a data structure used to represent a Trie in compact form where all nodes with one child are merged with their parent.

Suffix Tree:

It is a patricia tree corresponding to a given string.  It is a compact representation of a trie corresponding to the suffixes of a given string where all nodes with one child are merged with their parent.

Multi-Suffix Tree:

A multi suffix tree is a suffix tree extended to multiple strings by concatenating the strings.

Bucket Trie:

A bucket trie is a type of trie where leaf nodes are buckets which can hold k strings.  Thus the size of the bucket is generally taken to be fixed.

Compact trie:

It is a trie in which non-branching subtrees leading to leaf nodes are cut off.

Digital Tree:

A tree for storing strings in which nodes are organized by substrings common to two or more strings.

Digital Search Tree:

It is a data structure, a trie, which stores the strings in internal nodes, so there is no need for extra leaf nodes to store the strings.

Complete Binary Tree:

A full binary tree is a tree in which every node has zero or two children.  A perfect binary tree is a complete binary tree in which leaves are at the same depth.  Sometimes the perfect binary tree is also called the complete binary tree.

Tagged Union:

A tagged union is a data structure used to hold a value that could take on several different values of fixed type.  Only one of the types can be in use at any one time, and a tag field explicitly indicates which one is in use.  It is also called a variant, variant record, or disjoint union.  Like ordinary unions, tagged unions can save storage by overlapping storage areas for each type since only one is in use at a time.  In languages with tagged unions, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple data, left child and right child and the other of which is a leaf node, which contains no data and functions much like the null value in a language with pointers.

Binary Space Partitioning:

It is a method for recursively subdividing a space into convex sets.  This subdivision gives rise to a representation of the scene by means of a tree data structure.

Binary Space Partition Trees:

Binary Space Partition Trees (BSP) were introduced by Fuchs, Kedem and Naylor around 1980.  BSP tree is a hierarchical subdivisions of n dimensional space into convex subspaces.  Each node has a front and back leaf.  Starting off with the root node, all subsequent insertions are partitioned by the hyperplane of the current node.  In two-dimensional space, a hyperplane is a line.  In three-dimensional space, a hyperplane is a plane.  The end goal of a BSP tree is for the hyerplanes of the leaf nodes to be trivially behind or in-front of the parent hyperplane.

A quadtree is a tree data structure in which each internal node has up to four children.  Quadtrees are more often used to partition a two dimensional space by recursively subdividing it into four quadrants.  Some common applications of quadrees are image representation, spatial indexing etc.  Quadtrees are two dimensional analog of octrees.

Octrees:

An octree is a tree data structure mainly used for organizing 3-dimensional data.  Each node of an octree has eight children.

R-trees:

R-trees are tree data structures similar to B-trees, but are used for spatial access methods i.e. for indexing multi-dimensional information.  Each node of an R-tree has a variable number of entries.  Each entry within a non-leaf node stores two pieces of data; a way of identifying a child node and the bounding box of all entries within this child node.  A new element will go into the leaf node that requires the least enlargement in its bounding box.  The insertion and deletion algorithms use the bounding boxes from the nodes to ensure that nearby elements are placed in the same leaf node.  Different algorithms can be used to split nodes when they become too full, resulting in the “Quadratic” and “Linear” R-tree subtypes.

Hash Table:

A hash table is a data structure that provides fast lookup of a record indexed by a key where the domain of the key is too large for simple indexing; as would occur if an array were used.  Like arrays, hash tables can provide O(1) lookup with respect to the number of records in the table.  Hash tables are often used to implement associative arrays.

Parse Tree:

A parse tree is a grammatical structure represented as a tree data structure.  Grammar is the study of the rules governing the use of a language.  The subfields of grammar are phonetics, phonology, morphology, syntax and semantics.  Grammar is part of the general study of language called linguistics.

B+ Tree:

A B+ tree index takes the form of a balanced tree in which every path from the root to the tree leaf is of the same length.  Each non-leaf node in the tree has between ‘n/2’ and ‘n’ children, where n is fixed for a particular tree.  The B+ tree structure creates performance overhead on insertion and deletion and adds space overhead.  The space overhead is acceptable when we consider the performance benefits of the B+ tree structure.  Each node of a B+ tree contains a pointer and the associated search key value.  The pointer in the leaf node of the B+ tree points either to a file with the associated search key value or to a bucket of pointers. Each leaf can hold upto (n-1) values.  The minimum value that a leaf node may contains is (n-1)/2.  The non-leaf nodes of the B+ tree form a multilevel sparse index on the leaf nodes.  The structure of the non-leaf node is the same as the leaf node, except that all pointers are pointers to tree nodes.  A non-leaf node may hold upto ‘n’ pointers but must hold atleast (n/2) pointers.  ‘B’ in the ‘B+’ trees stands for balanced.  It is the balance property of B+ trees that ensures good performance for lookup, insertion and deletion of records.  The main difference between a B tree index and a B+ index is that a B tree eliminates the redundant storage of search key values.  A B tree allows search key value to appear only once.  Thus, B+ tree is preferred for its structural simplicity.

x Close