Binary search tree in Java with only one class

Question

I have written a BST using one class. Is my code okey or something could be better?

/**
* BST using one class
* @author Mateusz Stankiewicz
*/
public class Node {
private Comparable data; 
private Node left;
private Node right;

private static Node root;

/**
 * Tree constructor
 */
public Node() {
    root = null;
}

/**
 * Node constructor
 */
private Node(Comparable data) {
    this.data = data;
    left = null;
    right = null;
}

/**
 * Tree method to add new element
 * 
 * @param data is a new data we want to add to a tree
 */
public void addToTree(int data) {
    if (root == null)
        root = new Node(data);
    else
        add(root, data);
}

// Private method that add new element
private void add(Node target, Comparable data) {
    if (data.compareTo(target.data)<0) {
        if (target.left == null)
            target.left = new Node(data);
        else
            add(target.left, data);
    } else {
        if (target.right == null)
            target.right = new Node(data);
        else
            add(target.right, data);
    }

}

/**
 * Prints out tree nodes
 */
public void printTree() {
    print(root);
}

// Private recursive method to print a tree
private void print(Node n) {
    if (n.left != null)
        print(n.left);
    System.out.println(n.data);
    if (n.right != null)
        print(n.right);
}

public static void main(String[] args) {
    Node tree = new Node();
    tree.addToTree(1);
    tree.addToTree(7);
    tree.addToTree(3);
    tree.addToTree(4);
    tree.addToTree(2);
    tree.printTree();
}
}

Answer 1

There are however a couple of improvements and refactoring that you could definitely make. The problem in your logic is that a node is holding a reference to the root node, when it shouldn't. A node should only know what data it contains and what are its left and right nodes, nothing more (you could perhaps argue that, in some cases, it could also contain a reference to its parent).

• Never use raw types. In this case, you are using Comparable as a raw type. Since your Node class can hold data for every type, what you want is to make that class a typed class.

  public class Node<T extends Comparable<T>> {
      private T data; 
      private Node<T> left;
      private Node<T> right;
      // ...
  }
  

  This makes the rest of the code type-safe. In this case, you are saying that your node can contain data of a type T that is comparable with itself, for any type matching this.

  Making this change will show the problem with your design:

  private static Node<T> root;
  

  This won't compile anymore and it echoes to what I said in the beginning of this answer: this shouldn't exist in the first place. So you should delete it.

• Then, the default constructor, which is

  public Node() {
      root = null;
  }
  

  can also be removed: when constructing a node, you should just need to specify the value its going to hold. As such, your next private constructor should be made public. Furthermore, you don't need to explicitely set the left and right node to null since it will be their default value.

  public Node(T data) {
      this.data = data;
  }
  

• The method addToTree should be renamed add. Furthermore, it takes an int as argument when it should be made more generic: you can accept in your node any object of type T. You could then refactor it to the following. Note that I also added explicits curly braces: it isn't a good practice to omit them.

  public void add(T data) {
      if (data.compareTo(this.data) < 0) {
          if (left == null) {
              left = new Node<>(data);
          } else {
              left.add(data);
          }
      } else {
          if (right == null) {
              right = new Node<>(data);
          } else {
              right.add(data);
          }
      }
  }
  

  Your current code doesn't handle the case where you're adding an element that is already present in the tree. If this is intended, it should be documented because BST are allowed not to contain duplicated elements (and most do not).

• In the same way, printTree should be renamed print. Consider adding curly braces here also.

  public void print() {
      if (left != null) {
          left.print();
      }
      System.out.println(data);
      if (right != null) {
          right.print();
      }
  }
  

---

For now, you are accepting in your node any Comparable objects. It would be better to accept any type T but also accept a Comparator<T>. The reason is that you may want to have in your tree:

• data for which you have no control over so you can't make it Comparable (note: you could still wrap it in a Comparable delegate).
• the same type of data but ordered differently (e.g. String ordered by their length, or their lexicographic order...).

This would make your class even more generic since it wouldn't be restricted to Comparable objects.

Answer 2

There is no need for the nested ifs in your add function. Here is a simplified version:

public void addToTree(int data) {

   root = add(root, data);
}
private Node add(Node target, Comparable data) {

    if (target == null) 
        return new Node(data);

    if (data.compareTo(target.data) < 0) {
        target.left = add(target.left, data);
    else 
        target.right = add(target.right, data);

    return target;

}

---

In your inorder walk there is no need to check if both child's are null just let it go one depth more:

private void print(Node n) {   
    if(n == null) return;
    print(n.left);
    System.out.println(n.data);
    print(n.right);
}