Page 245 - DCAP407_DATA_STRUCTURE

Data Structure

13.1.2 Inserting in Binary Search Trees
To insert a new element in an existing binary search tree, first we compare the value of the new node
with the current node value. If the value of the new node is lesser than the current node value, we insert
it as a left sub-node. If the value of the new node is greater than the current node value, then we insert it
as a right sub-node. If the root node of the tree does not have any value, we can insert the new node as
the root node.
Algorithm for Inserting a Value in a Binary Search Tree
1. Read the value for the node that needs to be created and store it in a node called NEW.

2. At first, if (root! =NULL) then root = NEW.
3. If (NEW->value < root->value) then attach NEW node as a left child node of root, else attach NEW
node as a right child node of root.
4. Repeat steps 3 and 4 for creating the desired binary search tree completely.
When inserting any node in a binary search tree, it is necessary to look for its proper position in the
binary search tree. The new node is compared with every node of the tree. If the value of the node
which is to be inserted is more than the value of the current node, then the right sub-tree is considered,
else the left sub-tree is considered. Once the proper position is identified, the new node is attached as
the left or right child node. Let us now discuss the pseudo code for inserting a new element in a binary
search tree.
Pseudocode for Inserting a Value in a Binary Search Tree

//Purpose: Insert data object X into the Tree
//Inputs: Data object X (to be inserted), binary-search-tree node
//Effect: Do nothing if tree already contains X;
// otherwise, update binary search tree by adding a new node containing data object X
insert(X, node){
if(node = NULL){

node = new binaryNode(X,NULL,NULL)
return
}
if(X = node:data)
return
else if(X<node:data)
insert(X, node:leftChild)

else // X>node:data
insert(X, node:rightChild)
}

Consider figure 13.4. In this figure, 35 has to be inserted. First, 35 is compared with
the value of root node i.e., 10. As 35 is greater than 10, the right sub-tree is
considered. Now, 35 is compared with 22. As it is greater than 22, the search moves
to the right sub-tree. 35 is then compared with 34 and again the search moves to the
right sub-tree. Now, 35 is compared with 40, but as it is lesser than 40, we need to
move to the left branch of 40. But since the node 40 has no left child, 35 is attached
as the left child of 40. After the insertion of 35, the tree looks as shown in the figure
13.5.

238 LOVELY PROFESSIONAL UNIVERSITY