Function to add a node to binary search tree

Binary search tree (BST) is an ordered tree where each node has smaller values on the left sub tree and larger values on the right subtree. This is similar to binary search algorithm. And another useful fact is if you traverse the node in in-order method, the values of the tree will be in ascending order.

Binary Search Tree with root as 50

Now as you can see from the diagram on the left child and their children of root (which in this case is 50), values are 40, 20 and 45. All are less than 50. On the other hand, on the right sub tree 50, the values are 60, 55 and 78 - larger than 50.
And this rule follows for each and every node, not just root.

Now if we have to  add a node - let us 43, where shall we add it, in such a way that the tree will still remain as BST. The new node must be a leaf node (i.e. the node with no child nodes)

Let us traverse from root and find out where this new node fits. 43 is smaller than 50. Hence we must branch to left of 50. Now we get 40. 43 is larger than 40. Hence we must take a path to the right of 40. Here we come across 45. 43 is smaller than 45, so must take a path to the left. Luckily there are no nodes to the left of 45 (at last!). So we can attach our new node with 43, as left child of 45.

Similarly with the help of diagram, we can see that the nodes 59, 12,44 will be attached as right child of 55, left child of 20 and right child of 43 respectively.

Now how do we code all this?

We can either write a recursive function - which is easy to write but hard to understand, or we can write a non-recursive function. You must understand that, entire BST depends on recursive functions.

Anyways, for the sake of simplicity, let us first write a non-recursive function to add a node to BST.

• for any given node
• store node as prev_node
•  if new value is > node value
•  branch to right
• if new value is < node value
•  branch to left
• if new value == node value
• throw an error saying duplicate values are not allowed

 struct treenode
 { 
     int data; 
     struct treenode *left,*right;
 };

 tyepdef treenode *TREENODEPTR;

This is our structure for node of tree.  Next let us write a function createNode(). This function just allocates memory to a node and fills the data in it and sets left and right children to NULL. It returns the address of this newly created node.

TREENODEPTR createNode(int val) 
{ 
    TREENODEPTR newnode =  (TREENODEPTR)malloc(sizeof(struct treenode)); 
    newnode->data = val; newnode->left = NULL; 
    newnode->right = NULL; 
} 

 Here is the function to add this newnode to the tree TREENODEPTR. This function is non-recursive. 

void insertIntoBst(TREENODEPTR root, int newval)
{ 
 TREENODEPTR temp, prevnode,newnode = createNode(newval);
 /*we have an empty list. This node becomes root*/ 
if(root==NULL) 
 {
      root = newnode; 
      return root;
 } 
temp = root; 
while(1) 
{ 
    if (temp==NULL)
      { 
       ( newval > prevnode->data) ?(prevnode->right = newnode):(prevnode->left= newnode); 
       return root; 
      } 
    else 
    { 
         prevnode = temp; 
         if(newval > temp->data) 
            temp = temp->right;
         else if (newval < temp->data)
            temp = temp -> left; 
         else 
           { 
                  printf("Duplicate nodes are not allowed"); 
                 exit(1);
           }
     }
 } 
} 

But the function is so complicated. Because it should never be used. Any binary tree operation must be done using recursive function.

So let us write a recursive function to add a node to BST.

TREENODEPTR insertRecursive(TREENODEPTR node, int newval)
{
    TREENODEPTR newnode = createNode(newval);
    if(node==NULL)
       node = newnode;
    else if(newval>node->data)
       node->right = insertRec(node->right,newval);
    else if (newvaldata)
       node->left = insertRec(node->left,newval);
    else
       {
             printf("Duplicate nodes are not allowed");  
             exit(1);
    }
       
     return node;
} 

Isn't it elegant and short?