Heterogeneous Binary Search Tree

Question

I need to build a heterogeneous(Elements with different types) BST and be able to sort the elements but I do not know how to approach the problem.

I've got the binary tree code right here.

This is the node class

public class Node<T> {
  T data;
  Node<T> left;
  Node<T> right;

  Node(T data) {
    this.data = data;
    left = null;
    right = null;
  }
}

And this is the tree class.

public class Tree<T extends Comparable<T>> {
  private Node<T> root;
  StringBuilder result = new StringBuilder();

  public Tree() {
    root = null;
  }

  public Node<T> getRoot() {
    return root;
  }

  /**
   * Method that inserts nodes into the binary tree. If the tree is empty , a new root node is
   * initialized.
   *
   * @param root A node object.
   * @param dataBeingInserted The object to be inserted on the tree.
   * @return The root node object
   */
  private Node<T> insertNode(Node<T> root, T dataBeingInserted) {
    if (root == null) {
      root = new Node<>(dataBeingInserted);
      return root;
    }
   
    if (dataBeingInserted.compareTo(root.data) < 0) {
      root.left = insertNode(root.left, dataBeingInserted);
    } else if (dataBeingInserted.compareTo(root.data) > 0) {
      root.right = insertNode(root.right, dataBeingInserted);
    }
    return root;
  }

  public void insertNode(T dataBeingInserted) {
    root = insertNode(root, dataBeingInserted);
  }

  /**
   * Method that recursively searches for our element through the tree. If the value is present in
   * the root node , or there aren't any nodes in the tree , the method returns the root node. If
   * the value we're looking for is smaller than the root node's value , we search for our value in
   * the left subtree , otherwise we search for it in the right subtree.
   *
   * @param root A node object.
   * @param dataBeingSearched User's value.
   * @return Recursive call of the method.
   */
  private Node<T> searchTree(Node<T> root, T dataBeingSearched) {
    if (root == null || dataBeingSearched.compareTo(root.data) == 0) {
      return root;
    }
    if ((dataBeingSearched.compareTo(root.data) > 0)) {
      return searchTree(root.left, dataBeingSearched);
    }
    return searchTree(root.right, dataBeingSearched);
  }

  public Node searchTree(T dataBeingSearched) {
    return searchTree(root, dataBeingSearched);
  }

  /**
   * An implementation of the In-order traversal. First the left subtree is visited and printed
   * accordingly, then we visit and print the root and after that we visit and print the right
   * subtree.
   *
   * @param root The root node object.
   */
  private String inorderTraversal(Node root) {
    if (root == null) {
      return "";
    }
    inorderTraversal(root.left);
    result.append(root.data).append(" ");
    inorderTraversal(root.right);

    return result.toString();
  }

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

}

The problem with my tree right now is that I'm getting ClassCastException whenever any element is different than the root , because there what happens is the root defines the type of the tree and I can't fix that.

P.S Here is the snippet that gives me the error (I will post the whole main method for convenience.)

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Scanner;

public class Main {
  private static final Logger LOGGER = LoggerFactory.getLogger(Main.class);
  private static final Scanner SCANNER = new Scanner(System.in);

  public static void main(String[] args) {
    Tree tree = new Tree<>();
    tree.insertNode(50);
    tree.insertNode("30");
    tree.insertNode('b');
    tree.insertNode(69.3);
    tree.inorderTraversal();
    LOGGER.info("{}", tree.result);
  }
}

For example there the first insert is an Integer , after which I try to insert a String and right there it's giving me the ClassCastException , saying that String is incomparable with Integer.

Answer 1

I had a similar task in my java course. I used generics to define the tree. Then I created a tree of an interface, which is implemented by every node. The methods of the interface are then implemented in every node and this allowed me to compare and sort the objects. There is a simple example in this topic: simple heterogeneous k-ary tree in java (for creating network simulator)

I thought of the problem as of the products in a grocery store. Every product has id, brand, name, price but depending of the type of product they have to be cooled or have "best before" or need to be frozen or are not edible.

Answer 2

I think, the comments thoroughly elaborated that comparing any two objects is not sensibly possible. However, you can still implement such a tree by decoupling the comparison from the tree logic.

On the contrary, every client will be hit with the exact same problem you are facing right now, but some clients might have specific solutions that work for them. We'll look into that later.

First of all, Java already defines a Comparator interface that goes along with Comparable.

package java.util;

public interface Comparator<T> {
    int compare(T o1, T o2);
}

At the same time, let's rethink the tree interface. Basically, the requirements state that it should be able to accept just about any object, so it must have a method like

public void add(Object data);

At this point, there is no reason to use generics, since we can't actually make any restrictions. Even if there are other objects in the tree, it should still be able to accept any object.

Therefore, we could do something like

public class Tree {

    private Comparator<Object> comparator;
    private Node root;

    public Tree(Comparator<Object> comparator) {
        this.comparator = Objects.requireNonNull(comparator);
    }

    public void add(Object data) {
        root = insertNode(root, data);
    }

    private void insertData(Node root, Object dataBeingInserted) {
        // see below
    }

}

with no major changes to the Node class except that it's not generic anymore as well. Now, when comparing two objects in the insertNode method, we simply consult the Comparator instance instead of doing the comparison ourselves.

if (comparator.compare(dataBeingInserted, root.data) < 0) {
    root.left = insertNode(root.left, dataBeingInserted);
} else if (comparator.compare(dataBeingInserted, root.data) > 0) {
    root.right = insertNode(root.right, dataBeingInserted);
}

A client can use this Tree implementation with a Comparator that s/he limits to the types s/he knows may occur.

public static void main(String[] args) {
    Tree t = new Tree((o1, o2) -> {
        if (o1 instanceof Number && o2 instanceof String) {
            // numbers before strings
            return -1;
        }
        if (o1 instanceof Integer && o2 instanceof Integer) {
            return ((Integer) o1).compareTo((Integer) o2);
        }
        if (o1 instanceof String && o2 instanceof String) {
            return ((String) o1).compareTo((String) o2);
        }
        throw new ClassCastException("incompatible types: " + o1.getClass().getCanonicalName()
                + ", " + o2.getClass().getCanonicalName());
    });
    t.add("Hello");
    t.add(Integer.valueOf(1337));
}

As indicated by the ClassCastException, this solution is still not able to handle any possible type inherently. However, this Tree implementation can be used to handle every heterogeneous combination of types (as long as a client defines an appropriate Comparator).