Binary Search Tree (BST) – Part 1

Binary Search Tree (BST) is a data structure organized in such way that each node has comparable key and also satisfies condition that each key in the node is greater than any key in nodes of a left sub-tree and less than any key in the node of a right sub-tree.

Now take a look at array of numbrs: 10, 7, 1, 9, 3, 15, 12. If we insert them into BST in this order, BST wold look like:

bst

Now let’s try to implement BST, first will start with class that represents node of a tree:

 


public class Node {

   private int value;
   private Node leftNode;
   private Node rightNode;

   public Node(){
   }

   public Node(Node leftNode, Node rightNode){
      this.leftNode = leftNode;
      this.rightNode= rightNode;
   }
   public int getValue() {
      return value;
   }

   public void setValue(int value) {
     this.value = value;
   }

   public Node getLeftNode() {
     return leftNode;
   }

   public void setLeftNode(Node leftNode) {
     this.leftNode = leftNode;
   }

   public Node getRightNode() {
     return rightNode;
   }

   public void setRightNode(Node rightNode) {
     this.rightNode = rightNode;
   }

}

As you can see this class has its value and two attributes that represent left and right node.

Now we shall implement class that represents binary tree:


public class BinaryTree {
   private Node root;

   public BinaryTree(int rootValue){
      root = new Node();
      root.setValue(rootValue);
   }

   public Node getRoot() {
      return root;
   }

   public void setRoot(Node root) {
      this.root = root;
   }
}

 

This is even simpler class and it has only one node as an attribute – root node of the tree.

Now that we have tree structure implemented, it is time to implement some operations on it. First let’s implement a method that will simply print out tree node values in ascending order. In Node class we have method:


public void printTree(){
   if(leftNode!=null){
      leftNode.printTree();
   }
   System.out.println(value);
   if(rightNode!=null){
      rightNode.printTree();
   }else{
      return;
   }
}

To get ascending sorted value list of BST one should simple apply algorithm:
1. Go to the lowest left node of the tree, value of that element put in array
2. Go to the parent node and take value of that node an put it in the array
3. Repeat step 1 for the right sub tree of the parent node

Now if you look at the printTree() method you will see that it is using same logic with recursive calls of the same method.

And finally we just need to implement print method in BinaryTree class:


public void printTree(){
   root.printTree();
}

Second thing that we are going to implement is a method to add new node to the three with proper value. This method will accept value as an argument. Here we need to make sure that by inserting new node we still keep all the properties of BST. Take a look at the below method.

public void addNewValue(int newValue){
   if(newValue == value) {
      return;
   }else if(newValue < value){
      if(leftNode!=null){
         leftNode.addNewValue(newValue);
      }else{
         leftNode = new Node();
         leftNode.setValue(newValue);
     }
   } else{
      if(rightNode!=null){
         rightNode.addNewValue(newValue);
      }else{
         rightNode = new Node();
         rightNode.setValue(newValue);
     }
   }
}

Again we are applying recursion in this method, so in general new value is compared with value of current node, in case values are same no new node is added and return from the method is done (you can say that same element is found in the tree).

In case new value is less than value of current node and left node of the current node is not null we are calling same method but for left node, but if left node of current node does not exist this means that we found “place” for new value and so we create new node with new value and set it as a left node of the current node.

In case new value is greater than value of current node and right node is not null we are calling addNewValue method for right node, but if right node is null this means that we found “place” for new value and all we have to do is create new node and set it as a right node of the current node.

Finally for the adding new value to the BST we shall add new method to the BinaryTree class:


public void addNewValue(int newValue){
   root.addNewValue(newValue);
}

For the final part of this article we will implement two additional methods (I believe that explanation of code is not needed for those two methods):
1. Find node with minimal value in the BST


public Node findMin(){
   if(leftNode!=null){
      return leftNode.findMin();
   }else{
      return this;
   }
}

2. Find node with specific value


public Node findValue(int searchValue){
   if(searchValue<value){
     if(leftNode!=null){
        return leftNode.findValue(searchValue);
     }else{
        return null;
     }
   }else if(searchValue>value){
      if(rightNode!=null){
        return rightNode.findValue(searchValue);
      }else{
         return null;
      }
   }else{
      return this;
   }
}

This is end of the part one on BST … have a nice day 🙂

Posted in General Programming Tagged with: , , ,

Leave a Reply

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

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Subscribe for Newsletter

Categories