Binary Search Tree Complete Implementation in JAVA | Algorithms

Binary Search Tree Complete Implementation in JAVA | Algorithms
Delete(int n):

Com­pli­cated than Find() and Insert() oper­a­tions. Here we have to deal with 3 cases.
Node to be deleted is a leaf node ( No Children).
Node to be deleted has only one child.
Node to be deleted has two childrens.

Node to be deleted has two childrens.

You just can­not replace the deleteN­ode with any of its child.

Find The Successor:

Suc­ces­sor is the node which will replace the deleted node. Now the ques­tion is to how to find it and where to find it.

Suc­ces­sor is the smaller node in the right sub tree of the node to be deleted.

class Node{
int data;
Node left;
Node right;
}

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

public boolean find(int id){
Node current = root;
while(current!=null){
if(current.data==id){
return true;
}else if(current.data>id){
current = current.left;
}else{
current = current.right;
}
}
return false;
}
public boolean delete(int id){
Node parent = root;
Node current = root;
boolean isLeftChild = false;
while(current.data!=id){
parent = current;
if(current.data>id){
isLeftChild = true;
current = current.left;
}else{
isLeftChild = false;
current = current.right;
}
if(current ==null){
return false;
}
}
//if i am here that means we have found the node
//Case 1: if node to be deleted has no children
if(current.left==null && current.right==null){
if(current==root){
root = null;
}
if(isLeftChild ==true){
parent.left = null;
}else{
parent.right = null;
}
}
//Case 2 : if node to be deleted has only one child
else if(current.right==null){
if(current==root){
root = current.left;
}else if(isLeftChild){
parent.left = current.left;
}else{
parent.right = current.left;
}
}
else if(current.left==null){
if(current==root){
root = current.right;
}else if(isLeftChild){
parent.left = current.right;
}else{
parent.right = current.right;
}
}else if(current.left!=null && current.right!=null){

//now we have found the minimum element in the right sub tree
Node successor = getSuccessor(current);
if(current==root){
root = successor;
}else if(isLeftChild){
parent.left = successor;
}else{
parent.right = successor;
}
successor.left = current.left;
}
return true;
}

public Node getSuccessor(Node deleleNode){
Node successsor =null;
Node successsorParent =null;
Node current = deleleNode.right;
while(current!=null){
successsorParent = successsor;
successsor = current;
current = current.left;
}
//check if successor has the right child, it cannot have left child for sure
// if it does have the right child, add it to the left of successorParent.
// successsorParent
if(successsor!=deleleNode.right){
successsorParent.left = successsor.right;
successsor.right = deleleNode.right;
}
return successsor;
}
public void insert(int id){
Node newNode = new Node(id);
if(root==null){
root = newNode;
return;
}
Node current = root;
Node parent = null;
while(true){
parent = current;
if(id<current.data){
current = current.left;
if(current==null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current==null){
parent.right = newNode;
return;
}
}
}
}
public void display(Node root){
if(root!=null){
display(root.left);
System.out.print(" " + root.data);
display(root.right);
}
}
}

Use Recursion:
http://www2.hawaii.edu/~esb/2011fall.ics211/BinarySearchTree.java.html
public class BinarySearchTree<T extends java.lang.Comparable<T>> {
 
    private static class BinaryNode<T> {
      private T item;
      private BinaryNode<T> left;
      private BinaryNode<T> right;
    }
    protected BinaryNode<T> root = null; // null when tree is empty

   public void add(T value) {
     root = add(value, root);
    }
    protected BinaryNode<T> add(T value, BinaryNode<T> node) {
      if (node == null) {
          return new BinaryNode<T>(value);
      }
      if (value.compareTo(node.item) == 0) {
          // replace the value in this node with a new value
          node.item = value;
          // alternative code creates new node, leaves old node unchanged:
          //return new BinaryNode<T>(value, node.left, node.right);
      } else {
          if (value.compareTo(node.item) < 0) { // add to left subtree
        node.left = add(value, node.left);
          } else {    // add to right subtree
        node.right = add(value, node.right);
          }
      }
      return node;
    }
    public void remove(T key) {
      root = remove(key, root);
    }

    protected BinaryNode<T> remove(T value, BinaryNode<T> node) {
      if (node == null) { // key not in tree
          return null;
      }
      if (value.compareTo(node.item) == 0) { // remove this node
          if (node.left == null) { // replace this node with right child
        return node.right;
          } else if (node.right == null) { // replace with left child
        return node.left;
          } else {
        // replace the value in this node with the value in the
        // rightmost node of the left subtree
        node.item = getRightmost(node.left);
        // now remove the rightmost node in the left subtree,
        // by calling "remove" recursively
                    node.left = remove(node.item, node.left);
        // return node;  -- done below
          }
      } else {    // remove from left or right subtree
          if (value.compareTo(node.item) < 0) {
        // remove from left subtree
        node.left = remove(value, node.left);
          } else {    // remove from right subtree
        node.right = remove(value, node.right);
          }
      }
      return node;
        }

        protected T getRightmost(BinaryNode<T> node) {
      assert(node != null);
      BinaryNode<T> right = node.right;
      if (right == null) {
          return node.item;
      } else {
          return getRightmost(right);
      }
    }
  }
http://www.sanfoundry.com/java-program-implement-binary-search-tree/
http://www.algolist.net/Data_structures/Binary_search_tree
http://www.javabeat.net/binary-search-tree-traversal-java/
http://algs4.cs.princeton.edu/32bst/BST.java.html
Read full article from Binary Search Tree Complete Implementation in JAVA | Algorithms