Support us


to write
more tutorials




to create new
visualizers




to keep sharing
free knowledge
for you


every dollar helps
Need help with a programming assignment? Get affordable programming homework help.

Binary search tree. Adding a value

Adding a value to BST can be divided into two stages:

  • search for a place to put a new element;
  • insert the new element to this place.
Let us see these stages in more detail.

Search for a place

At this stage analgorithm should follow binary search tree property. If a new value is less, than the current node's value, go to the left subtree, else go to the right subtree. Following this simple rule, the algorithm reaches a node, which has no left or right subtree. By the moment a place for insertion is found, we can say for sure, that a new value has no duplicate in the tree. Initially, a new node has no children, so it is a leaf. Let us see it at the picture. Gray circles indicate possible places for a new node.

binary search tree places to add

Now, let's go down to algorithm itself. Here and in almost every operation on BST recursion is utilized. Starting from the root,

  1. check, whether value in current node and a new value are equal. If so, duplicate is found. Otherwise,
  2. if a new value is less, than the node's value:
    • if a current node has no left child, place for insertion has been found;
    • otherwise, handle the left child with the same algorithm.
  3. if a new value is greater, than the node's value:
    • if a current node has no right child, place for insertion has been found;
    • otherwise, handle the right child with the same algorithm.
Just before code snippets, let us have a look on the example, demonstrating a case of insertion in the binary search tree.

Example

Insert 4 to the tree, shown above.

BST insertion example, step 1
BST insertion example, step 2
BST insertion example, step 3
BST insertion example, result

Code snippets

The only the difference, between the algorithm above and the real routine is that first we should check, if a root exists. If not, just create it and don't run a common algorithm for this special case. This can be done in the BinarySearchTree class. Principal algorithm is implemented in the BSTNode class.

Java

public class BinarySearchTree {

     

 

      public boolean add(int value) {

            if (root == null) {

                  root = new BSTNode(value);

                  return true;

            } else

                  return root.add(value);

      }

}

public class BSTNode {
     

      public boolean add(int value) {

            if (value == this.value)

                  return false;

            else if (value <this.value) {

                  if (left == null) {

                        left = new BSTNode(value);

                        return true;

                  } else

                        return left.add(value);

            } else if (value > this.value) {

                  if (right == null) {

                        right = new BSTNode(value);

                        return true;

                  } else

                        return right.add(value);

            }

            return false;

      }

}

C++

bool BinarySearchTree::add(int value) {

      if (root == NULL) {

            root = new BSTNode(value);

            return true;

      } else

            return root->add(value);

}

 

bool BSTNode::add(int value) {

      if (value == this->value)

            return false;

      else if (value < this->value) {

            if (left == NULL) {

                  left = new BSTNode(value);

                  return true;

            } else

                  return left->add(value);

      } else if (value > this->value) {

            if (right == NULL) {

                  right = new BSTNode(value);

                  return true;

            } else

                  return right->add(value);

      }

      return false;

}

Visualizers

  1. Binary Search Tree (Insert) in Java Applets Centre

Recommended books

  1. Cormen, Leiserson, Rivest. Introduction to algorithms. (Theory)
  2. Aho, Ullman, Hopcroft. Data Structures and Algorithms. (Theory)
  3. Robert Lafore. Data Structures and Algorithms in Java. (Practice)
  4. Mark Allen Weiss. Data Structures and Problem Solving Using C++. (Practice)

Contribute to AlgoList

Liked this tutorial? Please, consider making a donation. Contribute to help us keep sharing free knowledge and write new tutorials.


Every dollar helps!

Partners Ads                

Leave a reply

Your name (optional):
Your e-mail (optional):
Message: