The Binary Search Tree is commonly used data structure in Computer Science. Below is a complete binary search tree implementation, including the standard methods used to find, insert, and delete nodes from the tree. In addition are methods to print tree structure as well as track of the number nodes (so the tree size can be determined without traversing).

Both the BdBst and TreeNode classes can be seen below. These can also be found on the Big Datums GitHub repo.

package com.bigdatums.trees;

import java.util.LinkedList;
import java.util.Queue;

public class BdBst<E extends Comparable<? super E>> {

    private TreeNode<E> root = null;
    private TreeNode<E> left = null;
    private TreeNode<E> right = null;
    private int treeSize = 0;

    public BdBst(){}

    public BdBst(TreeNode node){
        this.root = node;
    }

    public TreeNode<E> getRoot(){
        return root;
    }

    public int getSize() {
        return treeSize;
    }

    //increment tree size
    private void increment(){
        treeSize++;
    }

    //decrement tree size
    private void decrement(){
        treeSize--;
    }

    //recursive insert
    public void insert(E data) {
        root = insert(root, data);
        treeSize++;
        return;
    }

    private TreeNode<E> insert(TreeNode<E> root, E data){
        if(root == null) return new TreeNode<E>(data);

        if(data.compareTo(root.getData()) < 0) root.setLeft(insert(root.getLeft(), data));
        else if (data.compareTo(root.getData()) > 0) root.setRight(insert(root.getRight(), data));

        return root;
    }

    //iterative insert
    public boolean insertIter(E data){
        //insert as root if root is null
        if(root == null) {
            root = new TreeNode<E>(data);
            increment();
            return true;
        }

        TreeNode<E> curr = root;
        int comp;
        while(true) {
            comp = curr.getData().compareTo(data);
            if(comp > 0) {
                TreeNode<E> left = curr.getLeft();
                if(left == null) {
                    TreeNode<E> currLeft = new TreeNode<E>(data);
                    curr.setLeft(currLeft);
                    increment();
                    return true;
                }
                else curr = left;
            }
            else if (comp < 0) {
                TreeNode<E> right = curr.getRight();
                if(right == null) {
                    TreeNode<E> currRight = new TreeNode<E>(data);
                    curr.setRight(currRight);
                    increment();
                    return true;
                }
                else curr = right;
            }
            else return false;
        }
    }

    //recursive find
    public TreeNode<E> find(E data){
        return find(root, data);
    }

    public TreeNode<E> find(TreeNode<E> currentNode, E data){
        if(currentNode == null) return null;
        else if(currentNode.getData().equals(data)) return currentNode;
        else {
            int comp = currentNode.getData().compareTo(data);
            if(comp > 0) return find(currentNode.getLeft(), data);
            else return find(currentNode.getRight(), data);
        }
    }

    //iterative find
    public TreeNode<E> findIter(E data){
        if(root == null) return null;

        TreeNode<E> curr = root;
        int comp;
        while(true) {
            comp = curr.getData().compareTo(data);
            if(comp > 0) {
                TreeNode<E> left = curr.getLeft();
                if(left == null) return null;
                else curr = left;
            }
            else if (comp < 0) {
                TreeNode<E> right = curr.getRight();
                if(right == null) return null;
                else curr = right;
            }
            else return curr;
        }
    }

    //recursive delete
    public void delete(E data) {
        root = delete(root, data);
        decrement();
        return;
    }

    private TreeNode<E> delete(TreeNode<E> root, E data) {
        if(root == null) return root;

        if((data.compareTo(root.getData())) < 0) root.setLeft(delete(root.getLeft(), data));
        else if (data.compareTo(root.getData()) > 0) root.setRight(delete(root.getRight(), data));
        else {
            if(root.getLeft() == null) return root.getRight();
            else if (root.getRight() == null) return root.getLeft();
            else {
                TreeNode<E> smallest = getSmallest(root.getRight());
                root.setData(smallest.getData());
                root.setRight(delete(root.getRight(), smallest.getData()));
            }
        }
        return root;
    }


    //get smallest node in tree
    public TreeNode<E> getSmallest() {
        return getSmallest(root);
    }

    public TreeNode<E> getSmallest(TreeNode<E> node) {
        if(node == null) return null;
        if(node.getLeft() == null) return node;
        else return getSmallest(node.getLeft());
    }

    public void printTree(){
        if(root == null) {
            System.out.println("Empty Tree");
            return;
        }

        StringBuilder mesg = new StringBuilder();
        TreeNode<E> nodeLeft;
        TreeNode<E> nodeRight;

        Queue<TreeNode<E>> queue = new LinkedList<TreeNode<E>>();

        queue.add(root);
        while (!queue.isEmpty()){
            mesg.setLength(0);
            TreeNode<E> node = queue.remove();
            mesg.append("Node:");
            mesg.append(node.getData());

            nodeLeft = node.getLeft();
            nodeRight = node.getRight();
            if(nodeLeft!= null) {
                queue.add(nodeLeft);
                mesg.append(", Left:");
                mesg.append(nodeLeft.getData());
            }
            if(nodeRight != null) {
                queue.add(nodeRight);
                mesg.append(", Right:");
                mesg.append(nodeRight.getData());
            }

            //print node message
            System.out.println(mesg);
        }
    }

    public static void main(String[] args){
        BdBst x = new BdBst();
        x.insert(50);
        x.insert(60);
        x.insert(40);
        x.printTree();
    }

}
package com.bigdatums.trees;

public class TreeNode<E extends Comparable<? super E>> {
    private E data;
    private TreeNode<E> left = null;
    private TreeNode<E> right = null;

    public TreeNode(E e) {
        data = e;
    }

    public E getData(){
        return data;
    }

    public void setData(E e){
        data = e;
    }

    public TreeNode<E> getLeft(){
        return left;
    }

    public TreeNode<E> getRight(){
        return right;
    }

    public void setRight(TreeNode node){
         right = node;
    }

    public void setLeft(TreeNode node){
        left = node;
    }

    public boolean isLeaf(){
        if(left == null && right == null) return true;
        else return false;
    }

    public boolean hasBothChildren(){
        if (left != null && right != null) return true;
        else return false;
    }

    public String toString(){
        return data.toString();
    }
}

Leave a Reply

Java Binary Search Tree Implementation