Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Binary Search Tree - Java Implementation

People also ask

How is binary search tree implemented?

A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start searching from the root node; if the node to be inserted is less than the root node, then search for an empty location in the left subtree. Else, search for the empty location in the right subtree and insert the data.

Is binary search implemented in Java?

A binary search can be implemented either using an iterative or recursive approach. Arrays class in Java also provides the 'binarySearch' method that performs a binary search on an Array. In our subsequent tutorials, we will explore various Sorting Techniques in Java.

Is binary tree A binary search tree Java?

A binary tree is a recursive data structure where each node can have 2 children at most. A common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree.


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);
        }
    
    }