Generic implementation of binary search tree in Java

Question

The following is my binary search implementation in Java:

package com.solo.workouts.collections.Tree;

import com.solo.workouts.Implementors.Util;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.Objects;

/*
   @author soloworld

   @since 1.o

 */
public class BinarySearchTree<T> {
    private Comparator comparator;
    private  Node<T> root;

    private BinarySearchTree(Comparator comparator , T type) {

        this.comparator = comparator;

    }

    private BinarySearchTree(Comparator comparator) {
        this(comparator,null);
    }

    public static BinarySearchTree plantTree(Comparator comparator)

    {
        Objects.requireNonNull(comparator ,"requires an comparator . compartor canot be null");
    return new BinarySearchTree(comparator);
    }


    public void add(T element){
        Node<T> node =null;
        if(root==null)
        {
          node = new Node<>(element);
          root = node;

        }

        else  {

            Node<T> currentnode = root;

            while(currentnode !=null) {
                int result = compare(currentnode, new Node<>(element));

                if (result <= 0) {
                    if (currentnode.leftNode == null) {


                        currentnode.leftNode = new Node<>(element);
                        currentnode = null;
                    } else
                        currentnode = currentnode.leftNode;
                } else {
                    if (currentnode.rightNode == null) {
                        currentnode.rightNode = new Node<>(element);
                        currentnode = null;
                    } else
                        currentnode = currentnode.rightNode;
                }

            }
        }

    }

    public boolean containsElement(Object e){
    Objects.requireNonNull(e);
    Node<T> currentnode = new Node<>((T) e);

    return contains(currentnode);
    }

    private boolean contains(Node<T> node) {
        Objects.requireNonNull(node);

        Node<T> searchnode=null;
        Node<T> currentnode =root;

        while(searchnode==null &&
                currentnode!=null) {
            int value = compare(currentnode, node);

            if(value ==0)
                searchnode = currentnode;

            else if(value<0)
                currentnode = currentnode.leftNode;

            else
                currentnode = currentnode.rightNode;

        }

        return searchnode !=null;
    }

    private int compare(Node<T> currentnode, Node<T> element) {
        Objects.requireNonNull(currentnode);
        Objects.requireNonNull(element);
        Objects.requireNonNull(comparator);

        return comparator.compare(element.element,currentnode.element);

    }

    private Node<T> getnode(T element) {
        Objects.requireNonNull(element);
        Node<T> node = new Node<>(element,null,null);
        Node<T> currentnode = root;
        while (currentnode!=null && 0!= compare(currentnode,node)) {
            int value =  compare(currentnode,node);


             if(value <0) {

                currentnode = currentnode.leftNode;
            }else {
                currentnode = currentnode.rightNode;
            }


        }

        return currentnode;
    }


    private <T> Node<T>  getpredecessoe(Node<T> node) {
        Node<T> predecessor = null;
        return predecessor;
    }

    public T getsuccessor(T element) {
        Objects.requireNonNull(element);
        var node = getnode(element);
        var successor = getsuccessor(node);
        if(successor!=null)
             return successor.element;

        return null;


    }

    private  Node<T> getsuccessor(Node<T> node) {
        Node<T> successor = root;
        if(node.rightNode!=null) {
            successor = node.rightNode;

            while (successor.leftNode != null) {
                successor = successor.leftNode;
            }

        }
        else {
            successor = null;
            Node<T> cureentnode = root;
            while (cureentnode!= null &&0!= compare(cureentnode,node) ) {
                int compare = compare(cureentnode,node);

                 if(compare <=0){
                    successor = cureentnode;
                    cureentnode = cureentnode.leftNode;
                }

                else
                    cureentnode = cureentnode.rightNode;
            }

        }
        return successor;
    }



    public boolean deleteNode(T element) {
        var node =getnode(element);
        if(node== null)
              return false;

        if(node.leftNode ==null && node.rightNode == null)
            unlinkNode(node);


       else if(node.leftNode!=null && node.rightNode!=null) {
           var parent = getParent(node);
            var successor = getsuccessor(node);
            unlinkSuccessor(successor);
            successor.leftNode = node.leftNode;
            successor.rightNode = node.rightNode;
            linkSuccessorWithParent(parent,successor);
        }
       else {
           var parentNode = getParent(node);
           var childNode = node.leftNode!= null ? node.leftNode : node.rightNode;
           int compare = compare(parentNode,childNode);

           if(compare <=0)
               parentNode.leftNode = childNode;

           else
               parentNode.rightNode  = childNode;


           node = null;

        }

     return node == null;
    }

    private void linkSuccessorWithParent(Node<T> parent, Node<T> successor) {
       int compare =  compare(parent,successor);

       if(compare<=0)
           parent.leftNode = successor;
       else
           parent.rightNode = successor;
    }

    public void unlinkNode(Node<T> node) {
      var parent = getParent(node);

      Objects.requireNonNull(parent);
      Objects.requireNonNull(node);

      int compare = compare(parent,node);

      if(compare <=0)
          parent.leftNode = null;
      else
          parent.rightNode = null;


    }

    private  void unlinkSuccessor(final Node<T> successor) {
        var parent = getParent(successor);
        unlinkNode( successor);

        if(successor.rightNode != null)
            parent.leftNode = successor.rightNode;


    }

    private Node<T> getParent(Node<T> childnode) {
        var parentnode = root;
        var currentnode = root;
        Objects.requireNonNull(childnode);
        while (0!= compare(currentnode,childnode)) {
            parentnode = currentnode;
            int compare = compare(currentnode,childnode);

            if(compare<0)
                currentnode = currentnode.leftNode;

            else if(compare >0)
                currentnode = currentnode.rightNode;
        }

        return parentnode;
    }



    public void morrisTreewalk() {

    }


    private static class Node<T> {
        T element;
        Node<T> leftNode ;
        Node<T> rightNode;

        Node(T element, Node<T> leftNode, Node<T> rightNode) {
            this.element = element;
            this.leftNode = leftNode;
            this.rightNode = rightNode;
        }

        Node(T element) {
            this(element,null,null);
        }

    }


}

Even though this data structure passes basic test cases I was not sure what will be the performance if the amount of input is high. Also, if there is any optimisation, please tell.

Answer 1

If you are using a binary search tree, you may want to "balance" it, so that the tree does not get too deep, and searches are fast.

I suggest having a look at https://en.wikipedia.org/wiki/Tree_rotation

Answer 2

In this answer I'll comment on things like style, robustness or API design, not analyzing your algorithm.

package com.solo.workouts.collections.Tree;

The uppercase package name Tree doesn't follow the Java naming conventions, and this will confuse any colleage that you might cooperate with. 99% of the Java folks follow these conventions, so any deviation irritates.

private Comparator comparator;

You surely got a warning from your IDE about using a raw type. This declaration can benefit from generics, so the compiler already checks that the comparator is capable of comparing objects of type T:

private Comparator<? super T> comparator;

You need a comparator that can compare objects of type T, e.g. if you want a BinarySearchTree<Double>, a Comparator<Double> or a Comparator<Number> will do, but a Comparator<String> won't. And that's what <? super T> says.

private BinarySearchTree(Comparator comparator , T type) { ... }

I'd delete this constructor. The T type argument has a confusing name (you have to pass a concrete instance of T and not a type like Double.class) and isn't used at all. Let the private BinarySearchTree(Comparator comparator) { ... } constructor directly do the work.

private BinarySearchTree(Comparator comparator) { ... }

As already said for the field, add the generics specification here:

private BinarySearchTree(Comparator<? super T> comparator) {

In the add() method, you have numerous places where you create a new node for the new element: new Node<>(element). Especially the ones that you create just for the compare() call immediatelay after the comparison become garbage, and it happens repeatedly in the while loop. As all these nodes get exactly the same contents, it's enough to create one Node in the very beginning of the add() method, and use it in all the places instead of creation.

You use Objects.requireNonNull(e); quite often, probably to avoid getting a NullPointerException later, deep inside some method call stack. Of course, this also throws a NullPointerException, but from a controlled place (I'm typically too lazy to do that). It would be even better to always add a descriptive text which variable was null.

Consider rewriting the contains() method like this:

private boolean contains(Node<T> node) {
    Objects.requireNonNull(node);

    Node<T> currentnode = root;
    while(currentnode != null) {
        int value = compare(currentnode, node);

        if(value == 0) {
            return true;
        } else if(value < 0) {
            currentnode = currentnode.leftNode;
        } else {
            currentnode = currentnode.rightNode;
        }
    }
    return false;
}

I'm using an early return nested inside the while and if constructs. Some developers don't like that, but I think it makes the code clearer. But it's a metter of taste.

And I added curly braces, which I highly recommend to always do. It's too easy to think you can add a second statement to dependent block, but without the braces it's just one conditional statement, and the next one will be executed unconditionally.

One hint on formatting: your formatting is somewhat inconsistent. You're probably formatting your code by hand. IDEs like Eclipse have automated formatting tools, e.g. Ctrl-I corrects the indentation of the block you marked in the source file, and Ctrl-Shift-F completely reformats the code. Very useful, makes formatting easy.

Documentation: for such a general-use class, you should write Javadocs for the public constructors and methods. Your IDE will create the boilerplate, and you have to write down what the methods and their arguments do (not how they do it). Have a look at the Java API specification to get an idea of rather good Javadocs.

Answer 3

Java uses camelCasing. Every word after the first (or including the first if it's a class name) should be a capital. This make names easier to read, since it's clearer where the words start and end. All your names should follow this convention. For example: getSuccessor and getNode. You use proper camel casing in a couple places, but you're inconsistent.

---

Be more careful with your spacing.

while (currentnode!=null && 0!= compare(currentnode,node)) {

has a lot of inconsistent style that's making it harder to read than necessary. Putting spaces around operators is the cleanest way to go in my opinion. I also prefer to add spaces after commas:

while (currentnode != null && 0 != compare(currentnode, node)) {

Just be consistent.

---

While your indentation for containsElement is poor, the idea behind the function is good. You've put most of the logic away in a general function contains that could be reused elsewhere if needed, then just delegate to it in containsElement. This is much better than the alternative of duplicating logic.

---

---

Overall, there's nothing glaringly wrong with your logic, but your code is quite messy. You should practice making sure that your code is readable, for your own and other's sake. Have more consistent spacing after methods and if lines, ensure that your indentation is correct, and make sure your spacing around operators is less haphazard. Ideally, I should be able to glance at your code and "break it down" in my head easily using spacing alone. That's not as possible when there isn't a convention that can be relied on.