Leave a comment

How to create binary search tree?

Most of the people already know the algorithm to create a binary search tree. The basic idea is to insert new value in existing binary search tree. What if the given binary search tree doesn’t exist means it is null? We will create a node with the given value and that will be the root node. Once the root node is created, we have a binary search tree with one node, root node and next node will be set somewhere left or right depending upon whether the given value is lesser or larger then root node. We know that all new node will be inserted as leaf node only. The simple concept is that if the given value is lesser go left ward or else right ward.

Let me take an example for the people new to Binary Search Tree:

Let say we have given values  10 19 15 5 9 1 21. Now we need to create tree using these values. Transitions is as follows.

1. First value is 10 and we do not have tree yet (root is null), so the first node will be created with 10

+++ 10

Now we have a binary search tree with only node having value 10. Rest of the values will be inserted to this binary search tree one by one

2. Second value is 19 which is greater than 10 so 19 will be inserted to right side of 10. Tree will become like this:

+++ 10

+++++++ \

+++++++++ 19

3. Next value 15 is which is greater than 10 so, it will be inserted right side of 10 and again 15 is less than 19 so will be inserted left of 19. Remember all new nodes will be inserted as leaf node of existing binary search tree and later might will become internal node as in this case 19 was leaf node and as 15 came in it became internal node.

Please find the rest of the transition as follows:

tree

Now we have created binary search tree with given values. if you will look at all the values given in above example, all values are unique. What if a duplicate value is there? Most people try to avoid duplicates and do not allow duplicates. Binary search tree is used for searching purpose and if you find a value above in a tree, searching will be stopped at there and won’t go deeper down. However, few people allow duplicates and they can choose whether the duplicate value will go left or right. Let say we have one more 19 need to be inserted in above binary search tree. If we choose that duplicate value will go left, new 19 will be right child of 15 and if we choose that duplicate will go right, 19 will be left child of 21.

Here you go for the implementation. I am allowing duplicate (for just implementation purpose) and choose to go rightwards.


public class BSTUtils {
    public static BSTNode insert(BSTNode root, int val){
        BSTNode node = new BSTNode(val);
        if(root == null){
        root = node;
        }else{
        BSTNode currentNode = root;
        BSTNode parentNode = null;
        while(currentNode != null){
        parentNode = currentNode;
        if(val < currentNode.getVal())
        currentNode = currentNode.getLeft();
        else //if the value is equal or greater, will go rightwards
        currentNode = currentNode.getRight();
        }
        if(val < parentNode.getVal())
        parentNode.setLeft(node);
        else
        parentNode.setRight(node);
        }
        return root;
    }
}


public class BSTNode {
    private int val;
    private BSTNode left;
    private BSTNode right;
    public BSTNode(int val) {
        super();
        this.val = val;
    }
    public int getVal() {
        return val;
    }
    public void setVal(int val) {
        this.val = val;
    }
    public BSTNode getLeft() {
    return left;
    }
    public void setLeft(BSTNode left) {
        this.left = left;
    }
    public BSTNode getRight() {
        return right;
    }
    public void setRight(BSTNode right) {
        this.right = right;
    }
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: