A Binary Search Tree (BST) is a binary tree that is either empty or where every node contains a key and satisfies the following conditions:
1. The key in the left child of a node, if it exists, is less than the
key in its parent node.
2. The key in the right child of a node, if it exists, is greater than
the key in its parent node.
3. The left and right subtrees of a node are again BSTs.
The following are the operations commonly performed on a BST:
1. Searching a key
2. Inserting a key
3. Deleting a key
4. Traversing the tree
Inserting a
node
If the tree is empty, then the first entry, when inserted, becomes the root.
If 10 is to be inserted and since 10 is less than 25 it goes to into
left subtree of 10.
Insertion of 35, as 35 is greater than 25 it goes into right subtree of 25.
This process goes on for all the keys.
Insert 36, since 36 is greater than root 35 it goes into right subtree.
Now in right suntree we have 35, which is less than 36. So 36 goes into right
subtree of 35.
void Insert(int Key)
{
TreeNode *Tmp, NewNode;
NewNode = new BSTNode;
NewNode->Data = Key;
NewNode->Lchild = NewNode->Rchild = Null:
if(Root == Null)
{
Root = NewNode;
return;
}
Tmp = Root;
while(Tmp != Null)
{
if(Tmp->Data < Key)
{
if(Tmp->Lchild == Null)
{
Tmp->Lchild = NewNode;
return;
}
Tmp = Tmp->Lchild;
else if(Tmp->Rchild == Null)
{
Tmp->Rchild = NewNode;
return;
}
}
}
Tmp = Tmp->Rchild;
}
Searching for
a Key
To search for a target key, comparison is made between search key with
the key at the root of the tree. If it is the same, then the algorithm ends. If
it is less than the key at the root, search for the target key in the left
subtree, else search in the right subtree.
TreeNode Search(int Key)
{
TreeNode *Tmp = Root;
while(Tmp)
{
if(Tmp->Data == Key)
return Tmp;
else if(Tmp->data < Key)
Tmp = Tmp->Lchild;
else
Tmp = Tmp->Rchild;
}
return Null;
}
If a key 15 has to be searched in a Given BST. Compare 15 with root
element 25, as 15 is less than 25 search has to be done in left subtree of 25.
Now 10 is encountered, by comparing 15 with 10 as 15 is greater than 10
search has to be done in right subtree of 10.
Now 15 is encountered which is equal to search key so the element is
found.
If given element is not found in the tree or if the tree is empty a
Null is returned by the algorithm.
Deleting a
node
Let X is a node of key K to be deleted from BST T, if it exists in the
tree. Let Y be a parent node of X.
There are three cases when a node is to be deleted from a BST.
1. X is a leaf node.
2. X has one child.
3. X has both child nodes.
Case 1: X is a leaf node.
If leaf node has to be deleted, just change the child link of the
parent node as Null, and free the memory occupied by deleted node.
Case 2: X has one child.
There are two cases when X has one child
I. Node has only left subtree.
II. Node has only right subtree.
I. Node has
only left subtree.
If the node to be deleted has left subtree then link the left subtree
of the node to be deleted to its parent and free its memory
II. Node has
only right subtree.
If the node to be deleted has only right subtree then link the right
subtree of the node to be deleted to its parent amd free its memory.
Case 3: Node having both
subtrees
If the node to be deleted has both right and left
subtrees then search the best suitable node to be placed at the deleted node.
There are two alternatives:
1. One can search for the largest data in the
deleted node’s left subtree and replace the deleted node with it.
2. One can search for the smallest data from the
deleted node’s right sub tree and replace the deleted node with it.
