Just share our knowledge for the better future of this world

Binary Search Tree is a kind of Binary Tree. Let’s start with Tree. Tree is a data structure model which looks like a reversed tree, the root placed on top of the tree and the leaf placed on the bottom of the tree. The model will be looks like pyramid shape. Binary Tree is a tree which every leaves / nodes just have maximum two child leaves, that’s why we call it binary (base 2). Binary Search Tree… this kind of binary tree that have the position of leaves “sorted”. All of elements on the left of a leaf must be smaller than the leaf and all of elements on the right of a leaf must be bigger than the leaf. What about same value? that’s up to you to place it where.

Let’s look this example from wikipedia, “F” is the root of the tree. “B” is a left child of “F”. “G” is a right child of “F”. “B” is a parent of “A”. “B” also a parent of “D”.

Creating Binary Search Tree can’t use the Node which is used for Linked List, Stack, and Queue. Honestly, the Node can be used but the context will be different because the pointer to other Node we will named child. I also give additional pointer, “parent” for pointing the parent of the Node. Let’s see the implementation on Java Programming Language.

public class BinaryTreeNode {

    public BinaryTreeNode parent;
    public BinaryTreeNode leftChild;
    public BinaryTreeNode rightChild;

    private String info;

    public BinaryTreeNode(String info){
        this.parent = null;
        this.leftChild = null;
        this.rightChild = null;
        this.info = info;
    }

    public String getInfo(){
        return this.info;
    }

    public void setInfo(String info){
        this.info = info;
    }

}

Then after we have the Nodes we can construct the Binary Search Tree. Which the most important method is inserting Nodes. If the tree root is null (the tree is new) we just make the node as root. But if the tree is not empty, we must track or find the right place of that node. The concepts is to find an empty place that meet the rules of binary search tree.

1. If the value of the new node less than current node
   1. If the left child of current node is not empty, move current node to left child
   2. else, the left child of current node is new node
2. If the value of the new node equal or more than current node
   1. If the right child of current node is not empty, move the current node to right child
   2. else, the right child of current node is new node

public class BinarySearchTree {

    private BinaryTreeNode root;

    public BinarySearchTree(){
        this.root = null;
    }

    public void insertNode(BinaryTreeNode node){
        if (this.root == null){
            this.root = node;
        }
        else{
            trackPosition(node, this.root);
        }
    }

    private void trackPosition(BinaryTreeNode node, BinaryTreeNode start){
        String sInfo = start.getInfo();
        if (sInfo.compareTo(node.getInfo()) > 0){
            if (start.leftChild == null){
                start.leftChild = node;
                node.parent = start;
            }
            else{
                trackPosition(node, start.leftChild);
            }
        }
        else{
            if (start.rightChild == null){
                start.rightChild = node;
                node.parent = start;
            }
            else{
                trackPosition(node, start.rightChild);
            }
        }
    }

}

Related posts:

1. Binary Tree Traverse Java Source Code
2. Java Programming : Morse Code
3. Creating Node for Linked List C++ Source Code
4. Creating Linked List on Java I
5. Creating Stack from LinkedList on Java

2 Responses

Stay in touch with the conversation, subscribe to the RSS feed for comments on this post.

1. 

   Tyrone

   How to implement this on an interface?

   6 March 2010 at 16:17

   Reply
   • 

     I Made Krisna

     I think you can’t do that. because this is a class which isn’t abstract and this just for binary search tree logic example.

     If you still want to implement to an interface, you must change “class” to “interface” and remove the implementation code on each method.

     6 March 2010 at 17:43

     Reply