Binary Search Tree

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

To insert a new node into a BST, the keys should remain in proper order so that the resulting tree satisfies the definition of a BST.

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.