-2
\$\begingroup\$

I am working on creating a binary search tree for an assignment in college. So far, I've created the basic structure of the search tree and an iterator for it.

I'm having problems when it comes to calling on the iterator and creating a toString() method. I am getting NullErrorException and I'm struggling to figure out where the logic of my code is going wrong.

The BinarySearchTree:

import java.util.Iterator;

public class BinarySearchTree<T> implements BinarySearchTreeADT<T>, Iterable<T> {
    // DON'T FORGET TO CHANGE BACK TO PRIVATE
    public BinaryTreeNode<T> root;
    private int size;

    BinarySearchTree() {
        root = null;
        size = 0;
    }

    /**
     * Returns a reference to the target element if it is found in the binary search tree.
     * @param node        the node you are starting the search at
     * @param element     the element you are looking for
     */
    public BinaryTreeNode<T> find(BinaryTreeNode<T> node, Comparable<T> element) throws NonExistentKeyException {
        if (node == null) {
            throw new NonExistentKeyException("doesn't exist");
        }

        else {
            if (element.compareTo(node.getElement()) == 0) {
                return node;
            }

            else if (element.compareTo(node.getElement()) > 0) {
                return find(node.getRight(), element);
            }

            else {
                return find(node.getLeft(), element);
            }

        }
    }

    /** Adds an element to the correct spot in the tree or throws a duplicated key error if there is an element already there.
     * @param node        the node you are starting the search at
     * @param element     the element you are adding
     */
    public void add(BinaryTreeNode<T> node, T element) throws DuplicatedKeyException {

        BinaryTreeNode<T> addElement = new BinaryTreeNode(element);
        Comparable<T> elem = (Comparable<T>)element;


        if (node == null) {
            root = addElement;
            size++;
        }

        else if (elem.compareTo(node.getElement()) == 0) {
            throw new DuplicatedKeyException("duplicate");
        }

        else if (elem.compareTo(node.getElement()) < 0) {
            if (node.getLeft() == null) {
                node.setLeft(addElement); 
                size++;
            } 
            else {
                add(node.getLeft(), element);
            }
        }

        else {
            if (node.getRight() == null) {
                node.setRight(addElement);
                size++;
            }
            else {
                add(node.getRight(), element);
            }
        }
    }

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

    public boolean isEmpty() {
        return (size == 0);
    }

    public int size() {
        return size;
    }

    /**
     * Returns true if the element is contained in the tree.
     */
    public boolean contains(T element) {
        if (isEmpty()) { 
            return false;
        }
        else {
            return true;
        }
    }

    /**
     * Return an iterator over the binary search tree. 
     */
    public Iterator<T> iterator() {
        BinaryTreeIterator<T> myIter = new BinaryTreeIterator<T>(root, size);
        return myIter;
    }

/**
 * Returns a string representation of the elements in the binary search tree.
 */
    public String toString() {
        String s = "";

        BinaryTreeIterator<T> myIter = (BinaryTreeIterator<T>) this.iterator();

        while (myIter.hasNext()) {
            s += (String) myIter.next() + ", ";
        }

        return s;
    }

}

The Iterator:

import java.util.Iterator;

public class BinaryTreeIterator<T> implements Iterator<T> {

private BinaryTreeNode<T> root; // points to root of binary search tree
private T[] items;
private int current; // current position in the collection
private int size; // keeps of the number of elements in the binary search tree (number of elements in the collection)

public BinaryTreeIterator(BinaryTreeNode<T> root, int size) {
    this.root = root;
    this.size = 0;
    current = 0;
    inorder(root, items);
}

public boolean hasNext() {
      return (current < size);
}

public T next() {
    if (!hasNext()) {
        throw new NoSuchElementException("is empty");
    }
    current++;
    return items[current - 1];
}

protected void inorder (BinaryTreeNode<T> node, T[] array) {
    if (node != null) {
        inorder (node.getLeft(), array);
        array[size] = node.getElement();
        size++;
        inorder (node.getRight(), array);
        }
    }   
}

For the sake of the assignment, I need to use an array in the code for the iterator.

New contributor
user214274 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
  • 1
    \$\begingroup\$ Unfortunately code that isn't working right isn't appropriate for this site. \$\endgroup\$ – tinstaafl Dec 3 at 1:53
  • \$\begingroup\$ @tinstaafl is right. Questions about "how to fix compile-time errors, runtime errors, or incorrect results" are off-topic here. Please see the tour page for more details. Though just between you and me, items doesn't seem to be defined anywhere. \$\endgroup\$ – MJ713 Dec 3 at 2:32
  • \$\begingroup\$ Questions about code not working as intended is not ready for Code Review@SE. \$\endgroup\$ – greybeard Dec 3 at 7:03