How make an add Method with a BinarySearchTree in Java?

Question

I am having trouble with my add method, I believe that the error occurs in the parameters passed in the public method, however I'm not sure if my private helper method is also not adding the correct variables.

Here are the instructions to my addMethod

The add(E) method may additionally call the assignFirst() method to assign the first attribute in case it should be changed. The add helper method should now assign each node's "parent" and "next" references when a new node is created.

• The "parent" parameter should reference a newly created node's parent node, so when creating a new node, you can simply assign its parent to this parameter.

• The "prev" parameter should reference a newly created node's previous node, so when creating a new node, you can simply update the "next" references in the appropriate nodes. The tricky part is knowing what values to pass when you're calling the add helper method. Here's the logic:

• If the add helper return value is to be a right child, then that right child's previous node should be the same as its parent. The optional getPrevNode won't be helpful here since the previous node will be the new node's parent, and the new node isn't yet attached to the tree.

• If the add helper return value is to be a left child, then that left child's previous node could be determined by the optional getPrevNode method, asking it for the node that is before the current node parameter.

Here is my code:

public void add(E value)
{
    this.root = add(root, value, root, null);
    assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        node.parent = parent;
        node.next = prev;

        this.numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value, node , getPrevNode(node));
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value, node, node.parent);
    }
    return node;
}
private void assignFirst()
{
    BSTNode<E> node = root;
    while(node.left != null)
    {
        node = node.left;
    }
    first = node;
}
 private BSTNode<E> getPrevNode(BSTNode<E> node)
{
    if(node.left != null)
    {
        node = node.left;
        while(node.right != null)
        {
            node = node.right;
        }
        return node;
    }
    else if(node.parent != null)
    {
        if(node.parent.right == node)
        {
            return node.parent;
        }
        if(node.parent.left == node)
        {
            while(node.parent != null && node.parent.left == node)
            {
                node = node.parent;
            }
            if(node == root)
            {
              return null;
            }
            else
            {
              return node.parent;
            }
        }
    }
    return null;
}

Here is some background information, however I'm leaving some methods out since they're irrelevant to what I am trying to figure out. Therefore I am cutting it short.

public class BinarySearchTree<E extends Comparable<E>>
{
private BSTNode<E> root; // root of overall tree
private int numElements;
private BSTNode<E> first;
// post: constructs an empty search tree
public BinarySearchTree()
{
    this.root = null;
    this.numElements = 0;
}
 public class Iterator
{
    private BSTNode<E> currentNode;

    public Iterator()
    {
        currentNode = first;
    }

    public boolean hasNext()
    {
        return currentNode != null;
    }

    public E next()
    {
        E value = currentNode.data;
        currentNode = currentNode.next;
        return value;
    }
}
private static class BSTNode<E>
{
    public E data;
    public BSTNode<E> left;
    public BSTNode<E> right;
    public BSTNode<E> parent;
    public BSTNode<E> next;

    public BSTNode(E data)
    {
        this(data, null, null, null, null);
    }

    public BSTNode(E data, BSTNode<E> left, BSTNode<E> right, BSTNode<E> parent, BSTNode<E> next)
    {
        this.data = data;
        this.left = left;
        this.right = right;
        this.parent = parent;
        this.next = next;
    }
  }
}

Answer 1

This was a rigorous process, here's what I got

public void add(E value)
{
    this.root = add(root, value, root, null);
    assignFirst();
}
// post: value added to tree so as to preserve binary search tree
private BSTNode<E> add(BSTNode<E> node, E value, BSTNode<E> parent, BSTNode<E> prev)
{
    if (node == null)
    {
        node = new BSTNode<E>(value);
        node.parent = parent;
        if(prev == null)
        {
            node.next = parent;
        }
        else
        {
            node.next = prev.next;
            prev.next = node;
        }
        this.numElements++;
    }
    else if (node.data.compareTo(value) > 0)
    {
        node.left = add(node.left, value, node , getPrevNode(node));
    }
    else if (node.data.compareTo(value) < 0)
    {
        node.right = add(node.right, value, node, node);
    }
    return node;
}