addHelper.java

private void addHelper(Node parentPosition, Node newNode) {

        if (newNode.Key > parentPosition.Key) {// newNode's key is greater
                                       //than that of parent node go right

            if (parentPosition.Right == null) {//If the node is leaf
                parentPosition.Right = newNode;//append newNode to its Right
                newNode.Parent = parentPosition;//newNode's parent
                CurrentSize++;//increment tree's size
            } else {
                addHelper(parentPosition.Right, newNode);//If it is not a leaf
            }                                            //go down

        } else {
            if (parentPosition.Left == null) {
                parentPosition.Left = newNode;
                newNode.Parent = parentPosition;
                CurrentSize++;
            } else {
                addHelper(parentPosition.Left, newNode);
            }
        }

        CheckBalance(newNode);//Check the balance between children
    }