Вставьте метод для BST

Question

Мне удалось реализовать метод булевой вставки для бинарного дерева поиска. Он берет общие данные и вставляет ключ в BST. Мой код не допускает дублирования и возвращает false, если ключ уже представлен в BST. Возвращает true, если вставка прошла успешно.

Проблема в том, что, я думаю, это не увеличивает число элементов, присутствующих в BST, и может достигать только 2 элементов.

Я попытался отладить его и посмотреть, почему мои выходные данные и ожидания отключены на один.

Вот мои конструкторы и методы

public class BSTree<T extends Comparable<? super T>> implements Iterable {

    private int nelems;
    private BSTNode root;
    private BSTNode curr;
    private BSTNode keyHere;

    protected class BSTNode {

        T key;
        LinkedList<T> dataList;
        BSTNode left;
        BSTNode right;


        public BSTNode(BSTNode left, BSTNode right, LinkedList<T> dataList, T key) {
            //TODO
            this.left = left;
            this.right = right;
            this.key = key;
            setDataList(dataList);
        }

        public BSTNode(BSTNode left, BSTNode right, T key) {
            //TODO
            this.left = left;
            this.right = right;
            this.key = key;
            this.dataList = new LinkedList<T>();

        }

        public T getKey() {
            //TODO
            return this.key;
        }

        public BSTNode getLeft() {
            //TODO
            return this.left;
        }

        public BSTNode getRight() {
            //TODO
            return this.right;
        }

        public LinkedList<T> getDataList() {
            //TODO
            return this.dataList;
        }

        public void setleft(BSTNode newleft) {
            //TODO
            this.left = newleft;
        }

        public void setright(BSTNode newright) {
            //TODO
            this.right = newright;
        }

        public void setDataList(LinkedList<T> newData) {
            //TODO
            this.dataList = newData;
        }

        public void addNewInfo(T data) {
            //TODO
            if (data != null)
            {
                getDataList().addLast(data);
            }

        }

        public boolean removeInfo(T data) {


            return dataList.remove(data);

        }
    }

    public BSTree() {
        //TODO
        root = null;
        nelems = 0;
        curr = null;
        keyHere = null;

    }

Вот мой код для вставки

public boolean insert(T key) {


        if (key == null)
        {
            throw new NullPointerException();
        }

        if (findKey(key)) // this method returns true if key is in BST
        {
            return false;
        }

        if (getSize() == 0)
        {
            LinkedList<T> linked = new LinkedList<T>();
            BSTNode node = new BSTNode(null, null, linked,key);
            root = node;
            curr = root;
            nelems = 1;
        }
        else
         {
            if (curr.getKey().compareTo(key) < 0)
            {
                if(curr.getRight() != null)
                {
                    curr = curr.getRight();
                    insert(key);
                }
                else
                {
                    LinkedList<T> linked = new LinkedList<T>();
                    BSTNode node = new BSTNode(null,null,linked,key);
                    curr.setright(node);
                    nelems += 1 ;
                    curr = root;
                }

            }
            else
            {
                if (curr.getLeft() != null)
                {
                    curr = curr.getLeft();
                    insert(key);
                }
                else
                {
                    LinkedList<T> linked = new LinkedList<T>();
                    BSTNode node = new BSTNode(null,null,linked,key);
                    curr.setleft(node);
                    curr = root;
                    nelems += 1;
                }

            }
         }

        return true;

    }
public boolean findKey(T key) {

        if (key == null)
        {
            throw new NullPointerException();
        }

        if (getSize() == 0)
        {
            return false;
        }
        else if(curr.getKey().compareTo(key)!= 0)
        {
            if(curr.getKey().compareTo(key) < 0)
            {
                if (curr.getRight() != null)
                {
                    curr = curr.getRight();
                    findKey(key);
                }
                else
                {
                    this.curr = root;
                    return false;
                }
            }
            else
            {
                if (curr.getLeft() != null)
                {
                    curr = curr.getLeft();
                    findKey(key);
                }
                else
                {
                    this.curr = root;
                    return false;
                }
            }
        }
        else
        {
            this.keyHere = curr;
            this.curr = root;
            return true;
        }
        return true;

    }

Когда я вставляю значение в дерево, оно отслеживает первые 2 элемента, но после добавления третьего оно по какой-то причине останавливает элемент приращения. вот мои тестеры

public class BSTreeTester{
    BSTree<Integer> tree1;
    public void setUp() throws Exception {
        tree1 = new BSTree<Integer>();
    }
    public void testinsert() {
        tree1.insert(new Integer(100));
        assertEquals("The size of the tree should be 1", 1, tree1.getSize());
        assertEquals("The root of the tree should be 100", 100,
                (int)tree1.getRoot().getKey());

        tree1.insert(new Integer(200));
        assertEquals("The size of the tree shoul dbe 2", 2, tree1.getSize());
        assertEquals("The root of the tree should still be 100", 100,
                (int)tree1.getRoot().getKey());
        tree1.insert(new Integer(300));
        assertEquals("The size of the tree should be 3", 3, tree1.getSize());
        assertEquals("The root of the tree should still be 100", 100,
                (int)tree1.getRoot().getKey());

}

При вставке 3-го нового целого числа ожидаемое должно быть 3, но оно дает мне 2.