having a problem with my java BST search implementation

Question

I'm having problems with my bst search implementation method but I don't know why I keep getting an error once it gets to Alice? Not sure if its because it can't find it or if I implemented my insert incorrectly? Any help will be much appreciated.

import static org.junit.Assert.*;

import java.util.ArrayList;

/**
 * This is an implementation of a Binary Search Tree (BST).
 *
 */
public class BinarySearchTree {

    /**
     * Class containing key (name) for a node and right and left children
     */
    class Node {

        private String key;

        public String getKey() {
            return key;
        }

        public void setKey(String key) {
            this.key = key;
        }


        private Node left;

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }


        private Node right;

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        Node(String key) {
            this.key = key;
            right = null;
            left = null;
        }
    }

    /**
     * The root of the binary search tree (BST)
     */
    Node root;

    // Constructor 
    BinarySearchTree() {  
        root = null;  
    } 

    // Search for a given key in BST
    public Node search(String key) 
    { 
        Node node = null;
        node = searchRecursive(root, key);
        return node;
    }

    // Implement the search recursively in this helper function
    Node searchRecursive(Node root_node, String key) 
    { 
        //Node someNode = new Node(key);

            /**
             * TODO
             * 
             */
            Node someNode = new Node(key);
            if(root_node != null) {
                int comparison = someNode.getKey().compareTo(root_node.getKey());

                if(comparison < 0) {
                    root_node.left = insertRecursive(root_node.left, key);
                }else if(comparison > 0) {
                    root_node.right = insertRecursive(root_node.right, key);
                }
            }else{
                root_node = new Node(key);
            }
            return root_node;





    }

    // Insert a new Node with a key and value in BST
    public void insert(String key) {
        root = insertRecursive(root, key); 
    }

    // Implement the insert recursively in this helper function
    Node insertRecursive(Node root_node, String key) { 
        /**
         * TODO
         * 
         */
        Node someNode = new Node(key);
        if(root_node != null) {
        int comparison = someNode.getKey().compareTo(root_node.getKey());



        if(root_node == null) {
            root_node = new Node(key);
            return root_node;
        }

        if(comparison < 0) {
            root_node.left = insertRecursive(root_node.getLeft(), key);
        }else if(comparison > 0) {
            root_node.right = insertRecursive(root_node.getLeft(), key);
        }

        }
        return root_node;



    } 


    // A recursive inorder traversal of the BST 
    void inorder(Node root, ArrayList<String> strList) { 
        if (root != null) { 
            inorder(root.getLeft(), strList); 
            System.out.println(root.getKey()); 
            strList.add(root.getKey());
            inorder(root.getRight(), strList); 
        }
    }



    public static void main(String[] args) { 

        //For runtime computations
        long startTime, endTime;
        double duration = 0;


        startTime = System.currentTimeMillis();
        BinarySearchTree bst = new BinarySearchTree(); 
        /**
         * TODO:
         * Read in the names from the names.txt file, and
         * Insert all the names in the BST by calling:
         *  insert(name)
         */
        bst.insert("alice");
        bst.insert("zoe");
        bst.insert("alex");

        endTime = System.currentTimeMillis();
        duration += ((double) (endTime - startTime));
        System.out.println("BST insertion runtime is " + duration);

        /**
         * So an inorder traversal of the tree, ensure the result is 
         * order lexicographically
         */
        ArrayList<String> strList = new ArrayList<String>();
        bst.inorder(bst.root, strList);
        //Ensure the inorder traversal gives a 
        //lexicographic ordering of the names
        for (int i = 1; i < strList.size(); i++) {
            assertTrue(strList.get(i-1).compareTo(strList.get(i)) <= 0  );
        }

        /**
         * Verify that search returns the correct result
         */
        startTime = System.currentTimeMillis();
        Node n = bst.search("aaaa");
        assertEquals(n, null);
        endTime = System.currentTimeMillis();
        duration = ((double) (endTime - startTime));
        System.out.println("BST search runtime for aaaa is " + duration);


        startTime = System.currentTimeMillis();
        n = bst.search("alice");
        assertEquals(n.getKey(), "alice");
        endTime = System.currentTimeMillis();
        duration = ((double) (endTime - startTime));
        System.out.println("BST search runtime for alice is " + duration);


        startTime = System.currentTimeMillis();
        n = bst.search("zoe");
        assertEquals(n.getKey(), "zoe");
        endTime = System.currentTimeMillis();
        duration = ((double) (endTime - startTime));
        System.out.println("BST search runtime for zoe is " + duration);

    }
}

Answer 1

I think you have incorrect placement of braces in insertRecursive implementation when root is null.

Change

Node insertRecursive(Node root_node, String key) { 
    /**
     * TODO
     * 
     */
    Node someNode = new Node(key);
    if(root_node != null) {
    int comparison = someNode.getKey().compareTo(root_node.getKey());



    if(root_node == null) {
        root_node = new Node(key);
        return root_node;
    }

    if(comparison < 0) {
        root_node.left = insertRecursive(root_node.left, key);
    }else if(comparison > 0) {
        root_node.right = insertRecursive(root_node.right, key);
    }

    }
    return root_node;
}

to

Node insertRecursive(Node root_node, String key) { 
    /**
     * TODO
     * 
     */
    Node someNode = new Node(key);
    if(root_node != null) {
        int comparison = someNode.getKey().compareTo(root_node.getKey());

        if(comparison < 0) {
            root_node.left = insertRecursive(root_node.left, key);
        }else if(comparison > 0) {
            root_node.right = insertRecursive(root_node.right, key);
        }
    }else{
        root_node = new Node(key);
    }
    return root_node;
}

Your searchRecursive code also has a bug. Your current code says:

if(root_node != null) {
        System.out.println(root_node.key);
    }

    if(root_node == null || root_node.key.equals(key)) {

        return root_node;
    }
    if(key.compareTo(root_node.key) > 0) {
        return searchRecursive(root_node.left, key);
    }

    return searchRecursive(root_node.right, key);

here, if the key is greater than current node's key, you are moving left but instead you should move right and so goes with the below line. So change your method implementation to

Node searchRecursive(Node root_node, String key) 
{ 
    //Node someNode = new Node(key);

        /**
         * TODO
         * 
         */

     //Node someNode = new Node(key);
    if(root_node == null || root_node.key.equals(key)) {
        return root_node;
    }

    if(key.compareTo(root_node.key) > 0) {
        return searchRecursive(root_node.right, key);
    }

    return searchRecursive(root_node.left, key);   
}

Full Working Demo: https://ideone.com/3WuAXf

Update:

As @Maurice Perry mentions in the comment, you don't need to create a new node just to compare the key to be added to the current node's key.

You can completely remove this line from insertRecursive method

Node someNode = new Node(key);

and change

int comparison = someNode.getKey().compareTo(root_node.getKey());

to

int comparison = key.compareTo(root_node.getKey());