Mar 24, 2012

Insert a node in Binary Search Tree

C++
A node can be inserted in a binary search tree using two approaches
Double pointer approach
void insert(BinaryTreeNode **node, int data)
   {
      if(*node == NULL)
      {
        *node = getNewNode(data);
      }
      
      if(data == (*node)->data)
      {
        //do  nothing
      }
      else if(data < (*node)->data)
      {
        insert(&(*node)->left, data);
      }
      else
      {
        insert(&(*node)->right, data);
      }
   }

Single pointer approach
BinaryTreeNode* insert(BinaryTreeNode *node, int data)
    {
      if(node == NULL)
      {
        node = getNewNode(data);
        return node;
      }
      
      if(data == node->data)
      {
        //do  nothing
      }
      else if(data < node->data)
      {
        node->left = insert(node->left, data);
      }
      else
      {
        node->right = insert(node->right, data);
      }

      return node;
   }

Java
Java has only references which are synonymous to single pointers in C/C++. Inserting a node in java is achieved using the approach below. This is same as single pointer approach mentioned above

private BinaryTreeNode insert(BinaryTreeNode node, int data)
  {
    if(node == null)
    {
      node = new BinaryTreeNode(data);
      return node;
    }

    if(node.data == data)
    {
      //do nothing
    }
    else if(data < node.data)
    {
      node.left = insert(node.left, data);
    }
    else
    {
      node.right = insert(node.right, data);;
    }

    return node;
  }

No comments :

Post a Comment