BST Only Keeps Last Inserted Value and Makes it Root

Question

I'm trying to populate a binary search tree using an insert(), however when every I 'print' the contents of my BST, I only get the last item that was inserted into the BST. What do I need to fix to make sure all of my value are retaining in the BST?

From debuggin, I think that my problem is that my public void insert() is setting the new value to root evertime it is called. I don't know how to fix it?

Here is my BST CLass:

public class BinarySearchTree<T extends Comparable<T>> {

private class BinarySearchTreeNode<E>{
    public BinarySearchTreeNode<E> left, right;
    private E data;

    private BinarySearchTreeNode (E data) {
        this.data = data;
    }
}

private BinarySearchTreeNode<T> root;

public boolean isEmpty() {
    return root == null;
} 
private BinarySearchTreeNode<T> insert(T value, BinarySearchTreeNode<T> ptr) {
            if (ptr == null){ 
        ptr = new BinarySearchTreeNode<>(value); 
        return ptr; 
    }
    int compare = value.compareTo(ptr.data); //when ptr != null, this line and below should execute for each bstStrings.inster(x)
    /* pass the value (s1...sN) when compared to (ptr.data) to compare
     * when value and ptr.data == 0 re
     */
    if (compare == 0) {
        return ptr;
    }
    if (compare < 0) {
        while (ptr.left != null){
            ptr = ptr.left;
            if (ptr.left == null) {//found insertion point
                BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value);
                ptr = ptr.left;
                ptr = node;
                return ptr;
            }
        }
    }
    else {
        return insert(value, ptr.left);
    }
    if (compare > 0) {              
        if (ptr.right == null) {
            BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value);
            ptr = ptr.right;
            ptr = node;
            return ptr;
        } 
    }
    else {
        return insert(value, ptr.right);                    
    }
    return ptr;
}
public void insert(T value) {
    root = insert(value, root);  //****Where I believe the problem is******
} 
private void printTree(BinarySearchTreeNode<T>node){
    if(node != null){
        printTree(node.left);
        System.out.println(" " + node.data);
        printTree(node.right);
    }
}
public void printTree(){
    printTree(root);
    System.out.println();
}    
}

For added context here is my Main() where I am calling the insert() and trying to insert strings into the BST:

public class Main {

public static void main(String[] args) {

    BinarySearchTree<String> bstStrings = new BinarySearchTree<String>();

    String s = "Hello";
    String s1 = "World";
    String s2 = "This Morning";
    String s3 = "It's";

    bstStrings.insert(s);
    bstStrings.insert(s1);
    bstStrings.insert(s2);
    bstStrings.insert(s3);   //the only inserted value that is printed below

    bstStrings.printTree();

        System.out.println();
        System.out.println("You should have values above this line!");
}
}

Lastly my console output:

It's


You should have values above this line!

Answer 1

Some hints:

• I don't see any recursive calls inside insert. How would you traverse the BST without appropriate recursive calls (into the left or right subtree of the current node based on the value)? I do see some commented out code that looks like it would perform those calls. Why are they commented out?
• You're returning the newly inserted node, which you're then setting as root. This will set the root to point to the new node every time. I don't think that's what you want.
• If you're trying to handle the special case where the tree is empty, all you need to do is check to see if root is null, then set the new node to that.
• There really is no need to return ptr. Since your BST maintains a reference to root, you always have a reference to the root of the tree. Every time you insert, you start with the root and then recursively traverse the tree until you find a suitable place to insert the new node. If you really must return the reference, then you most certainly should not be setting root to that new node!

Here is some pseudocode to help you out:

// Recursive function that inserts a value into a BST
function insert(node, value):

    //Handles the case where you have no nodes in the tree, so root is null
    if node is null:
        node = new Node(value)

    // If the value is lesser than the current node's value, we need to insert it
    // somewhere in the right subtree
    else if value < node.value:
        if node.right is null:
           // This node doesn't have a right child, so let's insert the new node here
           node.right = new Node(value)
        else:
           // This node has a right child, so let's go further into this subtree to
           // find the right place to insert the new node
           insert(node.right, value)

    // If the value is greater than the current node's value, we need to insert it
    // somewhere in the left subtree
    else if value > node.value:
        if node.left is null:
           // This node doesn't have a left child, so let's insert the new node here
           node.left = new Node(value)
        else:
           // This node has a left child, so let's go further into this subtree to 
           // find the right place to insert the new node
           insert(node.left, value)
    else:
        // A node with this value already exists so let's print out an erro
        error("Node with that value already exists")

end function