Friday, May 1, 2015

Implementing Binary Search Tree in Java

I believe we all know what is a Binary Search Tree (also called ordered tree). I will explain the step-by-step implementation of BST in Java. First of all we will need a node class which will store data/info to be stored in node, parent of node, left and right child. We can also create a static nested class for that as well because this class will not be used by any other class. I will go with a separate class as it will keep the code clean and will also be easy to explain.
public class Node<T extends Comparable<T>> {
    private T data = null;
    private Node<T> left;
    private Node<T> right;
    private Node<T> parent;

    public Node(Node<T> parent, T data) {
        this.parent = parent;
        this.data = data;
    }

    public T getData() {
        return data;
    }

    public void setData(T data) {
        this.data = data;
    }

    public Node<T> getLeft() {
        return left;
    }

    public void setLeft(Node<T> left) {
        this.left = left;
    }

    public Node<T> getRight() {
        return right;
    }

    public void setRight(Node<T> right) {
        this.right = right;
    }

    public Node<T> getParent() {
        return parent;
    }

    public void setParent(Node<T> parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        String nodeInformation = "Data: " + data + " Parent: " + ( (parent != null) ? parent.data : "NULL") + " Left: " + ((left != null) ? left.data : "NULL") + " Right: " + ((right != null) ? right.data : "NULL");
        return super.toString();
    }
}

We want to be able to store any thing inside node (String, Integer and even our own class objects) and for that I would have used generics, also we want data stored in Node class comparable so we have used:
Node<T extends Comparable<T>&gt;

Next we will declare an interface ITree which will define the methods to be implemented by BST later on:
public interface ITree<T> {
    public boolean insert(T value);
    public T delete(T value);
    public void clear();
    public boolean contains(T value);
    public int size();
    public boolean validate();
    public java.util.Collection<T> toCollection();
}

Now we will move ahead with a class named BinarySearchTree which will implement this interface and body will look like:
public class BinarySearchTree<T extends Comparable<T>> implements ITree{
    protected Node<T> root;
    protected int size = 0;

    @Override
    public boolean insert(T value) {
        return false;
    }

    @Override
    public T delete(T value) {
        return null;
    }

    @Override
    public void clear() {

    }

    @Override
    public boolean contains(T value) {
        return false;
    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public boolean validate() {
        return false;
    }

    @Override
    public Collection toCollection() {
        return null;
    }
}

We have also declared two protected fields (as we want them available in derived classes as well) root and size of the tree. Next task is to provide the method implementations. We will consider insert first and will write two methods to insert a node to left or right of a parent.
private void insertNodeToRight(Node<T> parent, Node<T> child) {
    parent.setRight(child);
    child.setParent(parent);
    size++;
}

private void insertNodeToLeft(Node<T> parent, Node<T> child) {
    parent.setLeft(child);
    child.setParent(parent);
    size++;
}

Now we will write a method which will do the actual insertion of node to the tree. It will traverse through the tree to figure out place where a node can be inserted.
private Node<T> createNewNode(T value) {
 return (creator != null) ? (creator.createNewNode(null, value)) : (new Node<T>(null, value));
}
protected Node<T> insertValue(T value) {
 Node<T> newNode = createNewNode(value);

 // If root is null, assign
 if (root == null) {
  root = newNode;
  size++;
  return newNode;
 }

 Node<T> currentNode = root;
 while (currentNode != null) {
  if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left
   if(currentNode.getLeft() == null) {
    insertNodeToLeft(currentNode, newNode);
    break;
   }
   currentNode = currentNode.getLeft();
  } else {          // Greater than goes right
   if (currentNode.getRight() == null) {
    insertNodeToRight(currentNode, newNode);
    break;
   }
   currentNode = currentNode.getRight();
  }
 }

 return newNode;
}

Now this method will be actually called by our public insertion method as:
public boolean insert(T value) {
 Node<T> nodeAdded = this.insertValue(value);
 return (nodeAdded != null);
}

This completes the insertion functionality. Next we will work upon search functionality where it will search for a value in the tree. If the value is less than the value at current node it will go left else it will go right (assumption is we don't have duplicate).
public boolean contains(T value) {
 Node<T> node = searchAndGetNode(value);
 return (node != null);
}
protected Node<T> searchAndGetNode(T value) {
 Node<T> currentNode = root;
 while (currentNode != null && currentNode.getData() != null) {
  int valueComparison = value.compareTo(currentNode.getData());
  if (valueComparison == 0) {
   return currentNode;
  } else if (valueComparison < 0) {
   currentNode = currentNode.getLeft();
  } else {
   currentNode = currentNode.getRight();
  }
 }
 return null;
}

Next we can work on deletion of a node but before that we need to figure out which node will replace it. We don't have any concern if the node to be deleted has zero or one children, but in case it has both left and right children then we need to design our code carefully. In case node has both children we can delete the node and replace it with either rightmost (largest) child from left sub tree or leftmost (smallest) child from right sub tree. If we keep on using only one of these strategy then it can lead to skewed tree quickly.
private boolean toggleReplacementNodeSelection = true;
protected Node<T> getReplacementNode(Node<T> nodeToRemoved) {
 Node<T> replacement = null;
 if (nodeToRemoved.getLeft() != null && nodeToRemoved.getRight() == null) {
  // Using the less subtree
  replacement = nodeToRemoved.getLeft();
 } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() == null) {
  // Using the greater subtree (there is no lesser subtree, no
  // refactoring)
  replacement = nodeToRemoved.getRight();
 } else if (nodeToRemoved.getRight() != null && nodeToRemoved.getLeft() != null) {
  // Two children
  // Add some randomness to deletions, so we don't always use the
  // greatest/least on deletion
  if (toggleReplacementNodeSelection) {
   replacement = this.getLargestNodeInSubTree(nodeToRemoved.getLeft());
   if (replacement == null)
    replacement = nodeToRemoved.getLeft();
  } else {
   replacement = this.getSmallestNodeInSubTree(nodeToRemoved.getRight());
   if (replacement == null)
    replacement = nodeToRemoved.getRight();
  }
  toggleReplacementNodeSelection = !toggleReplacementNodeSelection;
 }
 return replacement;
}

Now after getting the replacement node we need to perform deletion. We need to update children of node to be deleted with new parent, update left and right child of replacement node and also update its parent. The method below does that:
protected void deleteAndReplaceNode(Node<T> nodeToDelete, Node<T> replacementNode) {
 if (replacementNode != null) {

  // Record left and right child of replacementNode for later use
  Node<T> leftChildOfReplacementNode = replacementNode.getLeft();
  Node<T> rightChildOfReplacementNode = replacementNode.getRight();

  // For left and right children of nodeToDelete, new parent is replacementNode
  Node<T> leftChildOfNodeToDelete = nodeToDelete.getLeft();
  if (leftChildOfNodeToDelete != null && !leftChildOfNodeToDelete.equals(replacementNode)) {
   replacementNode.setLeft(leftChildOfNodeToDelete);
   leftChildOfNodeToDelete.setParent(replacementNode);
  }
  Node<T> rightChildOfNodeToDelete = nodeToDelete.getRight();
  if (rightChildOfNodeToDelete != null && !rightChildOfNodeToDelete.equals(replacementNode)) {
   replacementNode.setRight(rightChildOfNodeToDelete);
   rightChildOfNodeToDelete.setParent(replacementNode);
  }

  // Update the link of parent of replacementNode as well. For the parent of replacementNode kids of replacementNode are its new kids.
  // In short grand-kids are kids now.
  Node<T> parentOfReplacementNode = replacementNode.parent;
  if (parentOfReplacementNode != null && !parentOfReplacementNode.equals(nodeToDelete)) {
   Node<T> leftChildOfParentOfReplacementNode = parentOfReplacementNode.getLeft();
   Node<T> rightChildOfParentOfReplacementNode = parentOfReplacementNode.getRight();

   // Check whether the replacementNode is left or right child of its parent.
   if (leftChildOfParentOfReplacementNode != null && leftChildOfParentOfReplacementNode.equals(replacementNode)) {
    parentOfReplacementNode.setLeft(rightChildOfReplacementNode);
    if (rightChildOfReplacementNode != null)
     rightChildOfReplacementNode.setParent(parentOfReplacementNode);
   } else if (rightChildOfParentOfReplacementNode != null && rightChildOfParentOfReplacementNode.equals(replacementNode)) {
    parentOfReplacementNode.setRight(leftChildOfReplacementNode);
    if (leftChildOfReplacementNode != null)
     leftChildOfReplacementNode.setParent(parentOfReplacementNode);
   }
  }
 }

 // Update the link in the tree from the nodeToRemoved to the replacementNode
 Node<T> parentOfNodeToDelete = nodeToDelete.getParent();

 if (parentOfNodeToDelete == null) {
  // We are deleting root node. So replacing the root node.
  root = replacementNode;
  if (root != null) root.parent = null;
 } else if (parentOfNodeToDelete.getLeft() != null && (parentOfNodeToDelete.getLeft().getData().compareTo(nodeToDelete.getData()) == 0)) {
  parentOfNodeToDelete.setLeft(replacementNode);
  if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
 } else if (parentOfNodeToDelete.getRight() != null && (parentOfNodeToDelete.getRight().getData().compareTo(nodeToDelete.getData()) == 0)) {
  parentOfNodeToDelete.setRight(replacementNode);
  if (replacementNode != null) replacementNode.parent = parentOfNodeToDelete;
 }
 size--;
}

Now this can be called by the public method as:
public T delete(T value) {
 Node<T> nodeToRemove = this.deleteValue(value);
 return ((nodeToRemove!=null)?nodeToRemove.getData():null);
}
protected Node<T> deleteValue(T value) {
 Node<T> nodeToRemoved = this.searchAndGetNode(value);
 if (nodeToRemoved != null) nodeToRemoved = deleteNode(nodeToRemoved);
 return nodeToRemoved;
}

Now similarly other methods can also be written.