Binary Search Tree Insertion

Binary Search Tree Insertion operation relies on the search operation. The aim of search operation in insertion is to find a node that can be parent of the new node. When we get the address of such a parent node for the node to be inserted, on the basis of the new node’s value it is decided whether it has to be inserted as left child or right child.

Points to consider

If tree is empty the new node will become the root node
If the node to be inserted exists in the Binary Search Tree, the insertion will not be done to avoid duplicate nodes.
The new node will always be added as a leaf node.
If parent is bigger than the new node, the new node will become its left child
If parent is smaller than the new node, the new node will become its right child

Binary Search Tree Insertion Procedure

In this procedure you will require two pointers CURR and PARENT. CURR will store the address of the current node which is compared with the VALUE that we want to insert in the Binary Search Tree. PARENT will store address of the parent node of the current node. ROOT pointer stores address of the root of the binary search tree. These steps will add a new node in a BST

Check the value of ROOT. If ROOT is NULL, it indicates that the BST is empty so the new node will become root node. SET CURR=NULL and PARENT=NULL go to step 4
Compare VALUE with ROOT->DATA.
- If VALUE is equal to the ROOT->DATA, Insertion procedure is terminated since the node is already existing in the BST
- If VALUE is less than ROOT->DATA, PARENT =CURR and CURR=CURR->LEFT
- If VALUE is greater than ROOT->DATA, PARENT =CURR and CURR=CURR->RIGHT
Compare VALUE with CURR->DATA and stop when CURR becomes NULL ( This will happen when CURR is updated with the child pointer of a leaf node)
- If VALUE is equal to the CURR->DATA, Insertion is procedure is terminated since the node is already existing in the BST
- If VALUE is less than CURR->DATA, PARENT =CURR and CURR=CURR->LEFT
- If VALUE is greater than CURR->DATA, PARENT =CURR and CURR=CURR->RIGHT
If CURR is NULL create a new node NEW with VALUE filled in the NEW->DATA and setting NEW->LEFT=NULL and NEW->RIGHT=NULL
If PARENT=NULL then make NEW as root node by setting ROOT=NEW and terminate procedure.
If VALUE<PARENT->DATA add NEW as left child of PARENT by setting PARENT->LEFT- NEW else make it is right child by setting PARENT->RIGHT=NEW

Example

The following insert operations will demonstrate how a Binary Search Tree insertion is done starting from the ROOT node.

INSERT 45

ROOT is NULL so the new node with value 45 will be added and ROOT pointer will get its address.

INSERT 60

ROOT 45 is smaller than 60, so 60 must be added on the right of 45. 45 is the parent node of 60 as its RIGHT pointer is NULL. So, 60 is added to the right of 45

INSERT 19

ROOT 45 is bigger than 19, so 19 must be added on the left of 45. 45 is the parent node of 19 as its LEFT pointer is NULL. So, 19 is added to the left of 45.

INSERT 35

ROOT 45 is bigger than 35, so 13 must be added on the left of 45. 45 has a left child node 19. 19 is smaller than 35, so 35 must be added to the right of 19. 19 is the parent node of 35 as its RIGHT pointer is NULL so, 35 is added to the right of 19.

INSERT 73

ROOT 45 is bigger than 73, So 73 must be added on the right of 45. 45 has a right child node 60. 60 is smaller than 73, so 73 must be added to the right of 60. 60 is the parent node of 73 as its RIGHT pointer is NULL. So, 73 is added to the right of 60.

INSERT 55

ROOT 45 is smaller than 55, so 55 must be added on the right of 45. 45 has a right child node 60. 60 is bigger than 55, so 55 must be added to the left of 60. 60 is the parent node of 55 as its LEFT pointer is NULL. So, 55 is added to the left of 60.

INSERT 10

ROOT 45 is bigger than 10, so 10 must be added on the left of 45. 45 has a left child node 19. 19 is bigger than 10, so 10 must be added to the left of 19. 19 is the parent node of 10 as its LEFT pointer is NULL. So, 10 is added to the left of 19.

admin