Binary Tree (JAVA implementation)

In computer science, a binary search tree, which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with keys less than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• Both the left and right subtrees must also be binary search trees.

Generally, the information represented by each node is a record rather than a single data element. However, for sequencing purposes, nodes are compared according to their keys rather than any part of their associated records.

wikipedia Article

/**
 * @author rajeevan
 */
public class BinaryTree <Key extends Comparable<? super Key>> {
   
    private Node root;
   
    class Node{
        private Key value;
        private Node left;
        private Node right;
       
       
        public Node(Key key){
            this.value=key;
        }
       
        public Node(Key key,Node left,Node right){
            this(key);
            this.left=left;
            this.right=right;
        }
       
        @Override
        public String toString(){
            return "value="+value+ " left="+left+" right="+right;
        }
       
        public void setLeft(Node left){
            this.left=left;
        }
       
        public void setRight(Node right){
            this.right=right;
        }
       
        public void setValue(Key value){
            this.value=value;
        }
       
        public Node getRight(){
            return right;
        }
       
        public Node getLeft(){
            return left;
        }
       
        public Key getValue(){
            return value;
        }
    }
  
    //create new binary tree starting with the root value
    public BinaryTree(Key value){
        this.root =new Node(value);
    }
   
    //create new binary tree with empty root
    public BinaryTree(){
       
    }
   
    //add a value to the binary Tree
    public void addValue(Key value){
        this.root=insertValue(value, root);
    }
   
    private Node insertValue(Key value,Node node){
    
        int compare=node.getValue().compareTo(value);

        if(compare==0){
            return node;
        }else if(compare>0){
            if(node.getLeft()!=null){
                node.setLeft(insertValue(value, node.getLeft()));
            }else{
                node.setLeft(new Node(value));
            }
        }else if(compare<0){
            if(node.getRight()!=null){
                node.setRight(insertValue(value, node.getRight()));
            }else{
                node.setRight(new Node(value));
            }
        }
        return node;
    }
   
    //search the tree for a value
    public boolean searchTree(Key value){
        return this.searchTree(value,root);
    }
   
    private boolean searchTree(Key value,Node node){
       
        if(node==null){
            return false;
        }

        if(node.getValue().equals(value)){
            return true;
        }else if(node.getValue().compareTo(value)<0){
            return searchTree(value,node.getRight());
        }else if(node.getValue().compareTo(value)>0){
            return searchTree(value, node.getLeft());
        }else{
            return false;
        }
    }
   
    public Key findMin() {
    return this.findMin(root);
    }

    private Key findMin(Node node){
        if(node.getLeft()==null){
            return node.getValue();
        }else{
            return findMin(node.getLeft());
        }
    }
   
    //return the minimum value of the tree
    public Key findMax() {
        return this.findMax(root);
    }

    private Key findMax(Node node){
        if(node.getRight()==null){
            return node.getValue();
        }else{
            return findMax(node.getRight());
        }
    }
   
    public void removeValue(Key value){
        this.removeValue(value,root);
    }
   
    private Node removeValue(Key value,Node node){
       if(node.getValue().compareTo(value)>0){
            node=removeValue(value,node.getLeft());
        }else if(node.getValue().compareTo(value)<0){
            node=removeValue(value,node.getRight());
        }else if(node.getLeft()!=null&& node.getRight()!=null){
             Key max=this.findMax(node.getLeft());
             node.setValue(max);
             node.setLeft(this.removeValue(max,node.getLeft())) ;
            
        }else{
            if(node.getLeft()==null&&node.getRight()==null){
                node=null;
            }else{
            Key k=node.getLeft()==null?node.getRight().getValue():node.getLeft().getValue();
            node.setValue(k);
            }
        }
        return node;
    }
   
   
}