0

Why is it that if I put

tree.addElement(10, tree.root);

it works, but if I do it again as in

tree.addElement(20, tree.root);

it doesn't work? I just want to add elements to the tree. What is wrong with my method? The error the compiler gives me is simply:

at LinkedBinarySearchTree.addElement(LinkedBinarySearchTree.java:68)

public void addElement(T element, BinaryTreeNode node) 
{
    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");

    Comparable<T> comparableElement = (Comparable<T>)element;

    if (isEmpty())
        root = new BinaryTreeNode<T>(element);
    else 
    {
        if (comparableElement.compareTo(root.getElement()) < 0)
        {
            if (root.getLeft() == null) 
                this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getLeft());
        }
        else
        {
            if (root.getRight() == null) 
                this.getRootNode().setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getRight());
        }
    }
    modCount++;

}

Here is the rest of the code:

 public class BinaryTreeNode<T>
{
protected T element;
protected BinaryTreeNode<T> left, right;

/**
 * Creates a new tree node with the specified data.
 *
 * @param obj the element that will become a part of the new tree node
 */
public BinaryTreeNode(T obj) 
{
    element = obj;
    left = null;
    right = null;
}

/**
 * Creates a new tree node with the specified data.
 *
 * @param obj the element that will become a part of the new tree node
 * @param left the tree that will be the left subtree of this node
 * @param right the tree that will be the right subtree of this node
 */
public BinaryTreeNode(T obj, LinkedBinaryTree<T> left, LinkedBinaryTree<T> right) 
{
    element = obj;
    if (left == null)
        this.left = null;
    else
        this.left = left.getRootNode();

    if (right == null)
        this.right = null;
    else
        this.right = right.getRootNode();
}

/**
 * Returns the number of non-null children of this node.
 *
 * @return the integer number of non-null children of this node 
 */
public int numChildren() 
{
    int children = 0;

    if (left != null)
        children = 1 + left.numChildren();

    if (right != null)
        children = children + 1 + right.numChildren();

    return children;
}

/**
 * Return true if this node is a leaf and false otherwise.
 *
 * @return true if this node is a leaf and false otherwise
 */
public boolean isLeaf() 
{
    return (numChildren() == 0);
}

/**
 * Return the element at this node.
 *
 * @return the element stored at this node
 */
public T getElement() 
{
    return element;
}

/**
 * Return the right child of this node.
 *
 * @return the right child of this node
 */
public BinaryTreeNode<T> getRight() 
{
    return right;
}

/**
 * Sets the right child of this node.
 *
 * @param node the right child of this node
 */
public void setRight(BinaryTreeNode<T> node) 
{
    right = node;
}

/**
 * Return the left child of this node.
 *
 * @return the left child of the node
 */
public BinaryTreeNode<T> getLeft() 
{
    return left;
}

/**
 * Sets the left child of this node.
 *
 * @param node the left child of this node
 */
public void setLeft(BinaryTreeNode<T> node) 
{
    left = node;
}

}

* Creates an empty binary search tree.
 */
public LinkedBinarySearchTree() 
{
    super();
}

/**
 * Creates a binary search with the specified element as its root.
 *
 * @param element the element that will be the root of the new binary
 *        search tree
 */
public LinkedBinarySearchTree(T element) 
{
    super(element);

    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");
}

/**
 * Adds the specified object to the binary search tree in the
 * appropriate position according to its natural order.  Note that
 * equal elements are added to the right.
 *
 * @param element the element to be added to the binary search tree
 * @return 
 */
public void addElement(T element, BinaryTreeNode node) 
{
    if (!(element instanceof Comparable))
        throw new NonComparableElementException("LinkedBinarySearchTree");

    Comparable<T> comparableElement = (Comparable<T>)element;

    if (isEmpty())
        root = new BinaryTreeNode<T>(element);
    else 
    {
        if (comparableElement.compareTo(root.getElement()) < 0)
        {
            if (root.getLeft() == null) 
                this.getRootNode().setLeft(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getLeft());
        }
        else
        {
            if (root.getRight() == null) 
                this.getRootNode().setRight(new BinaryTreeNode<T>(element));
            else
                addElement(element, root.getRight());
        }
    }
    modCount++;

}

/**
 * Adds the specified object to the binary search tree in the
 * appropriate position according to its natural order.  Note that
 * equal elements are added to the right.
 *
 * @param element the element to be added to the binary search tree
 */
public  LinkedBinarySearchTree(T element, BinaryTreeNode<T> node) 
{
    Comparable<T> comparableElement = (Comparable<T>)element;

    if (comparableElement.compareTo(node.getElement()) < 0)
    {
        if (node.getLeft() == null) 
            node.setLeft(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getLeft());
    }
    else
    {
        if (node.getRight() == null) 
            node.setRight(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getRight());
    }
}
4
  • If it is giving an error, how can it run once? Commented Jun 5, 2018 at 18:44
  • Could you give the full stack trace? It will help debug the problem Commented Jun 5, 2018 at 18:45
  • Show us the BinaryTreeNode constructor and getElement(). Commented Jun 5, 2018 at 18:46
  • I edited the code to add in more details. Commented Jun 5, 2018 at 19:00

1 Answer 1

2

I suspect you get a StackOverflowError since you are passing root.getLeft (and others similarly) instead of node.getLeft.

if (isEmpty())
    root = new BinaryTreeNode<T>(element);

The above creates a root the first time an element is inserted which is correct.

The traversal logic has to start from the current node passed to the method and not the root.

Here's a corrected one:

else 
{
    if (comparableElement.compareTo(node.getElement()) < 0)
    {
        if (node.getLeft() == null) 
            node.setLeft(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getLeft());
    }
    else
    {
        if (node.getRight() == null) 
            node.setRight(new BinaryTreeNode<T>(element));
        else
            addElement(element, node.getRight());
    }
}

Bonus: You can make the type parameter T bounded to get rid of the Comparable checks.

References:

Java- The meaning of <T extends Comparable<T>>?

Bounded Type Parameters Oracle Tutorial

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.