Binary Search Tree - Java Implementation

I'm writing a program that utilizes a binary search tree to store data. In a previous program (unrelated), I was able to implement a linked list using an implementation provided with Java SE6. Is there something similar for a binary search tree, or will I need to "start from scratch"?

You can use a TreeMap data structure. TreeMap is implemented as a red black tree, which is a self-balancing binary search tree.

According to Collections Framework Overview you have two balanced tree implementations:

• TreeSet
• TreeMap

Here is my simple binary search tree implementation in Java SE 1.8:

public class BSTNode
{
    int data;
    BSTNode parent;
    BSTNode left;
    BSTNode right;

    public BSTNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
        this.parent = null;
    }

    public BSTNode()
    {
    }
}

public class BSTFunctions
{
    BSTNode ROOT;

    public BSTFunctions()
    {
        this.ROOT = null;
    }

    void insertNode(BSTNode node, int data)
    {
        if (node == null)
        {
            node = new BSTNode(data);
            ROOT = node;
        }
        else if (data < node.data && node.left == null)
        {
            node.left = new BSTNode(data);
            node.left.parent = node;
        }
        else if (data >= node.data && node.right == null)
        {
            node.right = new BSTNode(data);
            node.right.parent = node;
        }
        else
        {
            if (data < node.data)
            {
                insertNode(node.left, data);
            }
            else
            {
                insertNode(node.right, data);
            }
        }
    }

    public boolean search(BSTNode node, int data)
    {
        if (node == null)
        {
            return false;
        }
        else if (node.data == data)
        {
            return true;
        }
        else
        {
            if (data < node.data)
            {
                return search(node.left, data);
            }
            else
            {
                return search(node.right, data);
            }
        }
    }

    public void printInOrder(BSTNode node)
    {
        if (node != null)
        {
            printInOrder(node.left);
            System.out.print(node.data + " - ");
            printInOrder(node.right);
        }
    }

    public void printPostOrder(BSTNode node)
    {
        if (node != null)
        {
            printPostOrder(node.left);
            printPostOrder(node.right);
            System.out.print(node.data + " - ");
        }
    }

    public void printPreOrder(BSTNode node)
    {
        if (node != null)
        {
            System.out.print(node.data + " - ");
            printPreOrder(node.left);
            printPreOrder(node.right);
        }
    }

    public static void main(String[] args)
    {
        BSTFunctions f = new BSTFunctions();
        /**
         * Insert
         */
        f.insertNode(f.ROOT, 20);
        f.insertNode(f.ROOT, 5);
        f.insertNode(f.ROOT, 25);
        f.insertNode(f.ROOT, 3);
        f.insertNode(f.ROOT, 7);
        f.insertNode(f.ROOT, 27);
        f.insertNode(f.ROOT, 24);

        /**
         * Print
         */
        f.printInOrder(f.ROOT);
        System.out.println("");
        f.printPostOrder(f.ROOT);
        System.out.println("");
        f.printPreOrder(f.ROOT);
        System.out.println("");

        /**
         * Search
         */
        System.out.println(f.search(f.ROOT, 27) ? "Found" : "Not Found");
        System.out.println(f.search(f.ROOT, 10) ? "Found" : "Not Found");
    }
}

And the output is:

3 - 5 - 7 - 20 - 24 - 25 - 27 - 
3 - 7 - 5 - 24 - 27 - 25 - 20 - 
20 - 5 - 3 - 7 - 25 - 24 - 27 - 
Found
Not Found

Here is a sample implementation:

import java.util.*;

public class MyBSTree<K,V> implements MyTree<K,V>{
    private BSTNode<K,V> _root;
    private int _size;
    private Comparator<K> _comparator;
    private int mod = 0;

    public MyBSTree(Comparator<K> comparator){
        _comparator = comparator;
    }

    public Node<K,V> root(){
        return _root;
    }

    public int size(){
        return _size;
    }

    public boolean containsKey(K key){
        if(_root == null){
            return false;
        }

        BSTNode<K,V> node = _root;

        while (node != null){
            int comparison = compare(key, node.key());

            if(comparison == 0){
                return true;
            }else if(comparison <= 0){
                node = node._left;
            }else {
                node = node._right;
            }
        }

        return false;
    }

    private int compare(K k1, K k2){
        if(_comparator != null){
            return _comparator.compare(k1,k2);
        }
        else {
            Comparable<K> comparable = (Comparable<K>)k1;
            return comparable.compareTo(k2);
        }
    }


    public V get(K key){
        Node<K,V> node = node(key);

        return node != null ? node.value() : null;
    }

    private BSTNode<K,V> node(K key){
        if(_root != null){
            BSTNode<K,V> node = _root;

            while (node != null){
                int comparison = compare(key, node.key());

                if(comparison == 0){
                    return node;
                }else if(comparison <= 0){
                    node = node._left;
                }else {
                    node = node._right;
                }
            }
        }

        return null;
    }

    public void add(K key, V value){
        if(key == null){
            throw new IllegalArgumentException("key");
        }

        if(_root == null){
            _root = new BSTNode<K, V>(key, value);
        }

        BSTNode<K,V> prev = null, curr = _root;
        boolean lastChildLeft = false;
        while(curr != null){
            int comparison = compare(key, curr.key());
            prev = curr;

            if(comparison == 0){
                curr._value = value;
                return;
            }else if(comparison < 0){
                curr = curr._left;
                lastChildLeft = true;
            }
            else{
                curr = curr._right;
                lastChildLeft = false;
            }
        }

        mod++;
        if(lastChildLeft){
            prev._left = new BSTNode<K, V>(key, value);
        }else {
            prev._right = new BSTNode<K, V>(key, value);
        }
    }

    private void removeNode(BSTNode<K,V> curr){
        if(curr.left() == null && curr.right() == null){
            if(curr == _root){
                _root = null;
            }else{
                if(curr.isLeft()) curr._parent._left = null;
                else curr._parent._right = null;
            }
        }
        else if(curr._left == null && curr._right != null){
            curr._key = curr._right._key;
            curr._value = curr._right._value;
            curr._left = curr._right._left;
            curr._right = curr._right._right;
        }
        else if(curr._left != null && curr._right == null){
            curr._key = curr._left._key;
            curr._value = curr._left._value;
            curr._right = curr._left._right;
            curr._left = curr._left._left;
        }
        else { // both left & right exist
            BSTNode<K,V> x = curr._left;
            // find right-most node of left sub-tree
            while (x._right != null){ 
                x = x._right;
            }
            // move that to current
            curr._key = x._key;
            curr._value = x._value;
            // delete duplicate data
            removeNode(x);
        }
    }


    public V remove(K key){
        BSTNode<K,V> curr = _root;
        V val = null;
        while(curr != null){
            int comparison = compare(key, curr.key());
            if(comparison == 0){
                val = curr._value;
                removeNode(curr);
                mod++;
                break;
            }else if(comparison < 0){
                curr = curr._left;
            }
            else{
                curr = curr._right;
            }
        }

        return val;
    }

    public Iterator<MyTree.Node<K,V>> iterator(){
        return new MyIterator();
    }

    private class MyIterator implements Iterator<Node<K,V>>{
        int _startMod;
        Stack<BSTNode<K,V>> _stack;

        public MyIterator(){
            _startMod = MyBSTree.this.mod;
            _stack = new Stack<BSTNode<K, V>>();

            BSTNode<K,V> node = MyBSTree.this._root;
            while (node != null){
                _stack.push(node);
                node = node._left;
            }
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }

        public boolean hasNext(){
            if(MyBSTree.this.mod != _startMod){
                throw new ConcurrentModificationException();
            }

            return !_stack.empty();
        }

        public Node<K,V> next(){
            if(MyBSTree.this.mod != _startMod){
                throw new ConcurrentModificationException();
            }

            if(!hasNext()){
                throw new NoSuchElementException();
            }

            BSTNode<K,V> node = _stack.pop();
            BSTNode<K,V> x = node._right;
            while (x != null){
                _stack.push(x);
                x = x._left;
            }

            return node;
        }
    }

    @Override
    public String toString(){
        if(_root == null) return "[]";

        return _root.toString();
    }

    private static class BSTNode<K,V> implements Node<K,V>{
        K _key;
        V _value;
        BSTNode<K,V> _left, _right, _parent;

        public BSTNode(K key, V value){
            if(key == null){
                throw new IllegalArgumentException("key");
            }

            _key = key;
            _value = value;
        }

        public K key(){
            return _key;
        }

        public V value(){
            return _value;
        }

        public Node<K,V> left(){
            return _left;
        }

        public Node<K,V> right(){
            return _right;
        }

        public Node<K,V> parent(){
            return _parent;
        }

        boolean isLeft(){
            if(_parent == null) return false;

            return _parent._left == this;
        }

        boolean isRight(){
            if(_parent == null) return false;

            return _parent._right == this;
        }

        @Override
        public boolean equals(Object o){
            if(o == null){
                return false;
            }

            try{
                BSTNode<K,V> node = (BSTNode<K,V>)o;
                return node._key.equals(_key) && ((_value == null && node._value == null) || (_value != null && _value.equals(node._value)));
            }catch (ClassCastException ex){
                return false;
            }
        }

        @Override
        public int hashCode(){
            int hashCode = _key.hashCode();

            if(_value != null){
                hashCode ^= _value.hashCode();
            }

            return hashCode;
        }

        @Override
        public String toString(){
            String leftStr = _left != null ? _left.toString() : "";
            String rightStr = _right != null ? _right.toString() : "";
            return "["+leftStr+" "+_key+" "+rightStr+"]";
        }
    }
}

This program has a functions for

1. Add Node

2. Display BST(Inorder)

3. Find Element

4. Find Successor

   class BNode{
   	int data;
   	BNode left, right;
   	
   	public BNode(int data){
   		this.data = data;
   		this.left = null;
   		this.right = null;
   	}
   }
   
   public class BST {
   	static BNode root;
   	
   	public int add(int value){
   		BNode newNode, current;
   		
   		newNode = new BNode(value);
   		if(root == null){
   			root = newNode;
   			current = root;
   		}
   		else{
   			current = root;
   			while(current.left != null || current.right != null){
   				if(newNode.data < current.data){
   					if(current.left != null)
   						current = current.left;
   					else
   						break;
   				}					
   				else{
   					if(current.right != null)
   						current = current.right;
   					else
   						break;
   				}											
   			}
   			if(newNode.data < current.data)
   				current.left = newNode;
   			else
   				current.right = newNode;
   		}
   		
   		return value;
   	}
   	
   	public void inorder(BNode root){
   		if (root != null) {
   			inorder(root.left);
               System.out.println(root.data);
               inorder(root.right);
           }
   	}
   	
   	public boolean find(int value){
   		boolean flag = false;
   		BNode current;
   		current = root;
   		while(current!= null){
   			if(current.data == value){
   				flag = true;
   				break;
   			}	
   			else if(current.data > value)
   				current = current.left;
   			else
   				current = current.right;
   		}
   		System.out.println("Is "+value+" present in tree? : "+flag);
   		return flag;
   	}
   	
   	public void successor(int value){
   		BNode current;
   		current = root;
   		
   		if(find(value)){
   			while(current.data != value){
   				if(value < current.data && current.left != null){
   					System.out.println("Node is: "+current.data);
   					current = current.left;
   				}
   				else if(value > current.data && current.right != null){
   					System.out.println("Node is: "+current.data);
   					current = current.right;
   				}					
   			}
   		}
   		else
   			System.out.println(value+" Element is not present in tree");
   	}
   
   	public static void main(String[] args) {
   		
   		BST b = new BST();
   		b.add(50);
   		b.add(30);
   		b.add(20);
   		b.add(40);
   		b.add(70);
   		b.add(60);
   		b.add(80);
   		b.add(90);
   		
   		b.inorder(root);
   		b.find(30);
   		b.find(90);
   		b.find(100);
   		b.find(50);
   		
   		b.successor(90);
   		System.out.println();
   		b.successor(70);
   	}
   
   }
   

---

Here is the complete Implementation of Binary Search Tree In Java insert,search,countNodes,traversal,delete,empty,maximum & minimum node,find parent node,print all leaf node, get level,get height, get depth,print left view, mirror view

---

import java.util.NoSuchElementException;
import java.util.Scanner;

import org.junit.experimental.max.MaxCore;

class BSTNode {

	BSTNode left = null;
	BSTNode rigth = null;
	int data = 0;

	public BSTNode() {
		super();
	}

	public BSTNode(int data) {
		this.left = null;
		this.rigth = null;
		this.data = data;
	}

	@Override
	public String toString() {
		return "BSTNode [left=" + left + ", rigth=" + rigth + ", data=" + data + "]";
	}

}


class BinarySearchTree {

	BSTNode root = null;

	public BinarySearchTree() {

	}

	public void insert(int data) {
		BSTNode node = new BSTNode(data);
		if (root == null) {
			root = node;
			return;
		}

		BSTNode currentNode = root;
		BSTNode parentNode = null;

		while (true) {
			parentNode = currentNode;
			if (currentNode.data == data)
				throw new IllegalArgumentException("Duplicates nodes note allowed in Binary Search Tree");

			if (currentNode.data > data) {
				currentNode = currentNode.left;
				if (currentNode == null) {
					parentNode.left = node;
					return;
				}
			} else {
				currentNode = currentNode.rigth;
				if (currentNode == null) {
					parentNode.rigth = node;
					return;
				}
			}
		}
	}

	public int countNodes() {
		return countNodes(root);
	}

	private int countNodes(BSTNode node) {
		if (node == null) {
			return 0;
		} else {
			int count = 1;
			count += countNodes(node.left);
			count += countNodes(node.rigth);
			return count;
		}
	}

	public boolean searchNode(int data) {
		if (empty())
			return empty();
		return searchNode(data, root);
	}

	public boolean searchNode(int data, BSTNode node) {
		if (node != null) {
			if (node.data == data)
				return true;
			else if (node.data > data)
				return searchNode(data, node.left);
			else if (node.data < data)
				return searchNode(data, node.rigth);
		}
		return false;
	}

	public boolean delete(int data) {
		if (empty())
			throw new NoSuchElementException("Tree is Empty");

		BSTNode currentNode = root;
		BSTNode parentNode = root;
		boolean isLeftChild = false;

		while (currentNode.data != data) {
			parentNode = currentNode;
			if (currentNode.data > data) {
				isLeftChild = true;
				currentNode = currentNode.left;
			} else if (currentNode.data < data) {
				isLeftChild = false;
				currentNode = currentNode.rigth;
			}
			if (currentNode == null)
				return false;
		}

		// CASE 1: node with no child
		if (currentNode.left == null && currentNode.rigth == null) {
			if (currentNode == root)
				root = null;
			if (isLeftChild)
				parentNode.left = null;
			else
				parentNode.rigth = null;
		}

		// CASE 2: if node with only one child
		else if (currentNode.left != null && currentNode.rigth == null) {
			if (root == currentNode) {
				root = currentNode.left;
			}
			if (isLeftChild)
				parentNode.left = currentNode.left;
			else
				parentNode.rigth = currentNode.left;
		} else if (currentNode.rigth != null && currentNode.left == null) {
			if (root == currentNode)
				root = currentNode.rigth;
			if (isLeftChild)
				parentNode.left = currentNode.rigth;
			else
				parentNode.rigth = currentNode.rigth;
		}

		// CASE 3: node with two child
		else if (currentNode.left != null && currentNode.rigth != null) {

			// Now we have to find minimum element in rigth sub tree
			// that is called successor
			BSTNode successor = getSuccessor(currentNode);
			if (currentNode == root)
				root = successor;
			if (isLeftChild)
				parentNode.left = successor;
			else
				parentNode.rigth = successor;
			successor.left = currentNode.left;
		}

		return true;
	}

	private BSTNode getSuccessor(BSTNode deleteNode) {

		BSTNode successor = null;
		BSTNode parentSuccessor = null;
		BSTNode currentNode = deleteNode.left;

		while (currentNode != null) {
			parentSuccessor = successor;
			successor = currentNode;
			currentNode = currentNode.left;
		}

		if (successor != deleteNode.rigth) {
			parentSuccessor.left = successor.left;
			successor.rigth = deleteNode.rigth;
		}

		return successor;
	}

	public int nodeWithMinimumValue() {
		return nodeWithMinimumValue(root);
	}

	private int nodeWithMinimumValue(BSTNode node) {
		if (node.left != null)
			return nodeWithMinimumValue(node.left);
		return node.data;
	}

	public int nodewithMaximumValue() {
		return nodewithMaximumValue(root);
	}

	private int nodewithMaximumValue(BSTNode node) {
		if (node.rigth != null)
			return nodewithMaximumValue(node.rigth);
		return node.data;
	}

	public int parent(int data) {
		return parent(root, data);
	}

	private int parent(BSTNode node, int data) {
		if (empty())
			throw new IllegalArgumentException("Empty");
		if (root.data == data)
			throw new IllegalArgumentException("No Parent node found");

		BSTNode parent = null;
		BSTNode current = node;

		while (current.data != data) {
			parent = current;
			if (current.data > data)
				current = current.left;
			else
				current = current.rigth;
			if (current == null)
				throw new IllegalArgumentException(data + " is not a node in tree");
		}
		return parent.data;
	}

	public int sibling(int data) {
		return sibling(root, data);
	}

	private int sibling(BSTNode node, int data) {
		if (empty())
			throw new IllegalArgumentException("Empty");
		if (root.data == data)
			throw new IllegalArgumentException("No Parent node found");

		BSTNode cureent = node;
		BSTNode parent = null;
		boolean isLeft = false;

		while (cureent.data != data) {
			parent = cureent;
			if (cureent.data > data) {
				cureent = cureent.left;
				isLeft = true;
			} else {
				cureent = cureent.rigth;
				isLeft = false;
			}
			if (cureent == null)
				throw new IllegalArgumentException("No Parent node found");
		}
		if (isLeft) {
			if (parent.rigth != null) {
				return parent.rigth.data;
			} else
				throw new IllegalArgumentException("No Sibling is there");
		} else {
			if (parent.left != null)
				return parent.left.data;
			else
				throw new IllegalArgumentException("No Sibling is there");
		}
	}

	public void leafNodes() {
		if (empty())
			throw new IllegalArgumentException("Empty");
		leafNode(root);
	}

	private void leafNode(BSTNode node) {
		if (node == null)
			return;
		if (node.rigth == null && node.left == null)
			System.out.print(node.data + " ");
		leafNode(node.left);
		leafNode(node.rigth);
	}

	public int level(int data) {
		if (empty())
			throw new IllegalArgumentException("Empty");
		return level(root, data, 1);
	}

	private int level(BSTNode node, int data, int level) {
		if (node == null)
			return 0;
		if (node.data == data)
			return level;
		int result = level(node.left, data, level + 1);
		if (result != 0)
			return result;
		result = level(node.rigth, data, level + 1);
		return result;
	}

	public int depth() {
		return depth(root);
	}

	private int depth(BSTNode node) {
		if (node == null)
			return 0;
		else
			return 1 + Math.max(depth(node.left), depth(node.rigth));
	}

	public int height() {
		return height(root);
	}

	private int height(BSTNode node) {
		if (node == null)
			return 0;
		else
			return 1 + Math.max(height(node.left), height(node.rigth));
	}

	public void leftView() {
		leftView(root);
	}

	private void leftView(BSTNode node) {
		if (node == null)
			return;
		int height = height(node);

		for (int i = 1; i <= height; i++) {
			printLeftView(node, i);
		}
	}

	private boolean printLeftView(BSTNode node, int level) {
		if (node == null)
			return false;

		if (level == 1) {
			System.out.print(node.data + " ");
			return true;
		} else {
			boolean left = printLeftView(node.left, level - 1);
			if (left)
				return true;
			else
				return printLeftView(node.rigth, level - 1);
		}
	}

	public void mirroeView() {
		BSTNode node = mirroeView(root);
		preorder(node);
		System.out.println();
		inorder(node);
		System.out.println();
		postorder(node);
		System.out.println();
	}

	private BSTNode mirroeView(BSTNode node) {
		if (node == null || (node.left == null && node.rigth == null))
			return node;

		BSTNode temp = node.left;
		node.left = node.rigth;
		node.rigth = temp;

		mirroeView(node.left);
		mirroeView(node.rigth);
		return node;
	}

	public void preorder() {
		preorder(root);
	}

	private void preorder(BSTNode node) {
		if (node != null) {
			System.out.print(node.data + " ");
			preorder(node.left);
			preorder(node.rigth);
		}
	}

	public void inorder() {
		inorder(root);
	}

	private void inorder(BSTNode node) {
		if (node != null) {
			inorder(node.left);
			System.out.print(node.data + " ");
			inorder(node.rigth);
		}
	}

	public void postorder() {
		postorder(root);
	}

	private void postorder(BSTNode node) {
		if (node != null) {
			postorder(node.left);
			postorder(node.rigth);
			System.out.print(node.data + " ");
		}
	}

	public boolean empty() {
		return root == null;
	}

}

public class BinarySearchTreeTest {
	public static void main(String[] l) {
		System.out.println("Weleome to Binary Search Tree");
		Scanner scanner = new Scanner(System.in);
		boolean yes = true;
		BinarySearchTree tree = new BinarySearchTree();
		do {
			System.out.println("\n1. Insert");
			System.out.println("2. Search Node");
			System.out.println("3. Count Node");
			System.out.println("4. Empty Status");
			System.out.println("5. Delete Node");
			System.out.println("6. Node with Minimum Value");
			System.out.println("7. Node with Maximum Value");
			System.out.println("8. Find Parent node");
			System.out.println("9. Count no of links");
			System.out.println("10. Get the sibling of any node");
			System.out.println("11. Print all the leaf node");
			System.out.println("12. Get the level of node");
			System.out.println("13. Depth of the tree");
			System.out.println("14. Height of Binary Tree");
			System.out.println("15. Left View");
			System.out.println("16. Mirror Image of Binary Tree");
			System.out.println("Enter Your Choice :: ");
			int choice = scanner.nextInt();
			switch (choice) {
			case 1:
				try {
					System.out.println("Enter Value");
					tree.insert(scanner.nextInt());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 2:
				System.out.println("Enter the node");
				System.out.println(tree.searchNode(scanner.nextInt()));
				break;

			case 3:
				System.out.println(tree.countNodes());
				break;

			case 4:
				System.out.println(tree.empty());
				break;

			case 5:
				try {
					System.out.println("Enter the node");
					System.out.println(tree.delete(scanner.nextInt()));
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

			case 6:
				try {
					System.out.println(tree.nodeWithMinimumValue());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 7:
				try {
					System.out.println(tree.nodewithMaximumValue());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 8:
				try {
					System.out.println("Enter the node");
					System.out.println(tree.parent(scanner.nextInt()));
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 9:
				try {
					System.out.println(tree.countNodes() - 1);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 10:
				try {
					System.out.println("Enter the node");
					System.out.println(tree.sibling(scanner.nextInt()));
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 11:
				try {
					tree.leafNodes();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}

			case 12:
				try {
					System.out.println("Enter the node");
					System.out.println("Level is : " + tree.level(scanner.nextInt()));
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 13:
				try {
					System.out.println(tree.depth());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 14:
				try {
					System.out.println(tree.height());
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 15:
				try {
					tree.leftView();
					System.out.println();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			case 16:
				try {
					tree.mirroeView();
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;

			default:
				break;
			}
			tree.preorder();
			System.out.println();
			tree.inorder();
			System.out.println();
			tree.postorder();
		} while (yes);
		scanner.close();
	}
}