Insertion in Binary Search Tree

Insertion in Binary Search Tree

Binary search tree is a data structure consisting of nodes, each node contain three information : value of the node, pointer or reference to left subtree and pointer or reference to right subtree. Property that distinguishes binary search tree from binary tree is that the data of all the nodes in the left sub-tree of the root node should be less than the data of the root and data in right subtree of the root node should be greater than or equal to data of the root. In today’s post we will see insertion in binary search tree.

binary search tree

For example :  Root node is with data = 10, data in the left subtree is: [5,1,6]; All data elements are < 10; Data in the right subtree is: [19,17,20].All data elements are > 10

Notice that property that data of all nodes on left subtree should be less and data on all in right subtree should be greater than root is followed at every node. So, for each node, it’s left subtree and right subtree are also binary search tree. This property helps to solve almost all problems on binary search tree recursively.

How to declare a node of a binary search tree?

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

Insertion in binary search tree

The structure and placement of each node depends on the order it is inserted into binary search tree. However, every insertion should leave binary search tree in correct state.  A new node is added to binary search tree based on value.

If the node is very first node to added to BST, create the node and make it root. However,if there are already existing nodes in BST,  follow the below steps :

  1. If value of current node is greater than value of new node, insert node in left subtree. If left child of current node is null,  attach new node as left child of current node. Else, move down the left child, now current node is left child.
  2. If value of current node is less than value  to  insert, insert node in right subtree. If right child of current node is null, attach new node as right child. Else, move down the right child. Right child become current node.

If you notice, above algorithm can be implemented recursively. At every node, problem reduces to subproblem which is to insert node in either left or right subtree depending on the relationship between value in current node and value to insert.

Let’s see an example and learn how to insert a node in BST.  Tree is given below and say we have to insert 8.

binary search tree

Check root, it is greater than value to insert, so node(8) will be on left subtree of root.

insert in binary search tree

Since left child is not null, left child will become current node, which is node(5).

5 is less than value to be inserted, hence 8 will be on the right subtree of node(5).  However, right child of node(5) is not null, hence right child(6) will become current node.

insert into binary search tree

At this point, node(6) is less than value (8), which means, node will be added to right subtree. As right child of node(6) is null, new node will be right child of it.

Final binary search tree will look like this.

insert in bst

Insert node in binary search tree : Recursive implementation

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTree {

    private Node root;

    public void BinarySearchTree(){
        root = null;
    }

    public class Node {
        private int value;
        private  Node left;
        private Node right;

        public Node(int value) {
            this.value = value;
            this.left = null;
            this.right = null;
        }
    }

    public void insert(int value){
        this.root =  insertNode(this.root, value);
    }

    private Node insertNode(Node root, int value){
        if(root == null){
            //if this node is root of tree
            root = new Node(value);
        }
        else{
            if(root.value > value){
                //If root is greater than value, node should be added to left subtree
                root.left = insertNode(root.left, value);
            }
            else{
                //If root is less than value, node should be added to right subtree
                root.right = insertNode(root.right, value);
            }
        }
        return root;
    }
}

Test class

package com.company.BST;

/**
 * Created by sangar on 10.5.18.
 */
public class BinarySearchTreeTests {
    public static void main (String[] args){
        BinarySearchTree binarySearchTree = new BinarySearchTree();

        binarySearchTree.insert(7);
        binarySearchTree.insert(8);
        binarySearchTree.insert(6);
        binarySearchTree.insert(9);
        binarySearchTree.insert(3);
        binarySearchTree.insert(4);

        binarySearchTree.inorderTraversal();

    }
}

What is complexity to insert a node in binary search tree?  At every node, we split the tree into two and discard the half of the tree. So recurrence relation is T(n) = T(n/2) + 1 which gives complexity to be O(log n). However, there is big assumption in here, which is binary search tree is balanced and there almost equal nodes on both side of each node, which may or may not be the case. In worst case, all nodes on BST are on one side of root node. When a new node is inserted, in worst case, we will scan all n nodes of tree. Hence, worst case complexity to insert a node in binary search tree is O(n).

There is another problem which comes with any recursive solution : danger of stack overflow. As number of nodes grow in binary search tree and if tree gets skewed, we may end up with n stack frames on stack.  In production, this n can be in millions and even billions. Depending of the size of each stack frame, we may run out of stack frames sooner or later. To get the gravity of problem of skewed binary search tree understand that for 1 billion nodes, in balanced BST, only 9 stack frames will be required where as for completely skewed BST, 1 billion stack frames will be required.

Insert in binary search tree : Iterative implementation

public void insertIterative(int value){
        if(this.root == null){
            this.root  = new Node(value);
        }
        else{
            Node currentNode = root;
            Node parent = null;
            while(currentNode != null){
                parent = currentNode;
                if(currentNode.value > value) {
                    currentNode = currentNode.left;
                }
                else{
                    currentNode = currentNode.right;
                }
            }

            //Parent cannot be null here
            if(parent.value > value){
                parent.left = new Node(value);
            }
            else {
                parent.right = new Node(value);
            }
        }
    }

How do you know that your insertion is correct? Best way is to traverse the tree in inorder way. In Inorder traversal we visit left subtree of node first before visiting root node and in last visit right subtree. This traversal should give nodes of tree in sorted order. If that’s the case, insertion function is working fine.

    private void inorder(Node root){
        if(root == null) return;

        inorder(root.left);
        System.out.println(root.value);
        inorder(root.right);
    }

Complexity of inorder traversal of BST is O(n) as we visit every one at least once. Above implementation is recursive, in future posts, we will be working on iterative implementation of all traversals of binary search tree.

Please share if there is something wrong or missing. We would be glad o hear from you in comments, mails or any other channel. If you are willing to share you knowledge and help thousands of learners across world, please reach out to us on communications@algorithmsandme.com