Binary Search Tree : Insertion Hackerrank problem solution

Binary Search Tree : Insertion Hackerrank

You are given a pointer to the root of a binary search tree and a value to be inserted into the tree. Insert this value into its appropriate position in the binary search tree and return the root of the updated binary tree. You just have to complete the function.

Input Format

You are given a function,

node * insert (node * root ,int value)
{

}

node is defined as :

struct node
{
int data;
node * left;
node * right;
}node;

Output Format

Return the root of the binary search tree after inserting the value into the tree.

Sample Input

4
/ \
2 7
/ \
1 3

The value to be inserted is 6.

Sample Output

4
/ \
2 7
/ \ /
1 3 6

Solution

Case 1: The binary tree is empty
The new node will be the root.
Case 2: The value is greater than current root node, and right subtree is not empty.
Go to the right subtree.
Case 3: The value is greater than current root node, and right subtree is empty.
Add the new node in root->right.
Case 2: The value is smaller or equal to the current root node and left subtree is not empty.
Go to the left subtree.
Case 3: The value is smaller or equal to the current root node and left subtree is empty.
Add the new node in root->left.

/*
Node is defined as 

typedef struct node
{
   int data;
   node * left;
   node * right;
}node;

*/


node * insert(node * root, int value)
{
   if(root==NULL){
       node *n=new node();
       n->data=value;
       n->left=NULL;
       n->right=NULL;
       root=n;
   }
    else if(root->data>value){
       root->left=insert(root->left, value);
          }
    else if(root->data<value){
       root->right=insert(root->right, value);
          }
    
   return root;
}
node *insert(node *root, int value) {
  node *new_node = new node();
  new_node->data = value;
  new_node->left = NULL;
  new_node->right = NULL;

  if (!root) { // Case 1
    root = new_node;
    return root;
  }
  node *current_root = root;
  while (1) {
    if (current_root->data > value) {
      if (current_root->left) // case 2
        current_root = current_root->left;
      else { // case 3
        current_root->left = new_node;
        break;
      }
    } else {
      if (current_root->right) // case 4
        current_root = current_root->right;
      else { // case 5
        current_root->right = new_node;
        break;
      }
    }
  }
  return root;
}
 /* Node is defined as :
 class Node 
    int data;
    Node left;
    Node right;
    
    */

static Node Insert(Node root,int value)
    {
        if(root == null) //can just insert straight into root as tree is empty
            {
                root = new Node();
                root.data = value;
        }
        else if(root.data > value) //value should go on left
            {
                if(root.left == null)
                {
                        Node left = new Node();
                        left.data = value;
                        root.left = left;
                }
                else //keep looking, strictly on left as value is smaller than root
                {
                     Insert(root.left, value);
                }
           
        }
        else //value should go on right (or equal to root, but i believe this is guaranteed to not be in input data)
            {
                if(root.right == null) //place for value found
                {
                        Node right = new Node();
                        right.data = value;
                        root.right = right;
                }
                else //keep looking, strictly to right of root as the value is greater
                {
                     Insert(root.right, value);
                }
        }
        return root;
    }

A web developer(Front end and Back end), and DBA at csdamu.com. Currently working as Salesforce Developer @ Tech Matrix IT Consulting Private Limited. Check me @about.me/s.saifi

Leave a reply:

Your email address will not be published.