Inserting a Node in Binary Search Tree

Insertion in a BST (Binary Search Tree) means you are inserting a new node / element to the Binary Search Tree and by doing so the keys should remain properly ordered.

I assume you know about Binary Search Tree. If not Read it from here.

Now let’s take an example and insert nodes in BST
50   30   60   20   40   70

Lets us start with 50 , it is first element hence becomes our root Node.

BST

Now next element is 30, which is smaller than 50. So it will become the left child of the Node.

BST

Now turn for the third element 60. As 60 > 50 … therefore it will be inserted as the right child of the Node.

BST




Next element in the list is 20. And 20 < 50. So move to the left. Root node already have a left child (30) , So now compare 20 with 30. You will find that 20 < 30 therefore we will move to its left and As the place for left child is vacant here , the new node (20) is inserted here. BST

Next element to be inserted is 40. So here also we start comparing from the root node and look out for its place to insert. Starting from root node, 50 (40<50). Then moving towards left (40>30). Then going towards right, it dont have right child so new node inserted here.

BST

Then our last element 70. Follow the same process and it will be inserted as right child of node 60. See below.

BST

Now as you understood the whole concept, So take a look on the Algo of inserting a new node in Binary Search Tree (BST)

Algorithm

  1. Allocate memory to new node, Assign value and make left / right child of new node = null.
  2. Locate parent of new node.
    • currentNode = root
    • parent = null
    • Repeat until currentNode =null
      • If newNode < currentNode, then currentNode = currentNode = currentNode's left child
      • If newNode > currentNode, then currentNode = currentNode = currentNode’s right child
  3. If parent = null (tree empty)
    • newNode = root, Exit
  4. If newNode < parent
    • parent’s left child = newNode, Exit
  5. If newNode > parent
    • parent’s right child = newNode, Exit

Leave a Reply

Your email address will not be published. Required fields are marked *