I'm new to Java and programming in general. The code works, mostly. It can do everything except for when I input the following:

• Sequence: d, e, f, a, b, c, g, h, i, j.

• Search for: b or c

I can't seem to find any issue with the code but have narrowed it down to the insertNode module/class, it seems like when users key in a, b, c after d, e, f, only node a register on the left side.

import java.util.Arrays;
import java.util.Scanner;
import java.lang.reflect.Method;

public class BinarySearchTreeTestStackOverflow {

    class Node {
        String stringData;
        Node leftChild;
        Node rightChild;
        Node(String stringData) {
            this.stringData = stringData;
            leftChild = rightChild = null;
        }
    }

    //root node for the binary tree
    Node root;

    //Constructor method
    public BinarySearchTreeTestStackOverflow() {
        root = null;
    }

    //Insert method for new values in the tree
    public void insert(String key) {
        root = insertNode(root, key);
    }

    //Insert recursive call for inserting from the root, in the right place
    public Node insertNode(Node node, String key) {

        if (node == null) {
            node = new Node(key);

            return node;
        }

        if (key.compareTo(node.stringData) < 0) {
            node.leftChild = insertNode(node.leftChild, key);

        } else if (key.compareTo(root.stringData) > 0) {
            node.rightChild = insertNode(node.rightChild, key);

        }
        return node;
    }



    //Find method asking for the node to find
    public Node find(String key) { //takes user input and turns it into a node
        Node node = findNode(root, key);
        System.out.println("print key to find: "   key);
        return node;
    }

    //Find recursive method using the root node.
    public Node findNode(Node node, String key) {

        if (key.compareTo(node.stringData) == 0) {

            return node;
        }




        //check up on findNodeMethod
        if (key.compareTo(node.stringData) <= 0) {

            if (node.leftChild == null) {
                return null;
            } else {
                return findNode(node.leftChild, key);
            }

        } else if (key.compareTo(node.stringData) > 0) {


            if (node.rightChild == null) {
                return null;
            } else {
                System.out.println("went right"); //toDelete
                return findNode(node.rightChild, key);
            }
        }
        return null;
    }



    public static void main(String[] args) {
        BinarySearchTreeTestStackOverflow binaryTree = new BinarySearchTreeTestStackOverflow();
        Scanner scanner = new Scanner(System.in);
        for (int i = 1; i <= 10; i  ) {

            System.out.print("Enter string "   i   " for the tree: ");
            binaryTree.insert(scanner.nextLine());
        }


        System.out.print("Enter the value to be searched: ");
        String key = scanner.nextLine(); //correct, verified using -  System.out.println("key to be searched: "  key);

        Node node = binaryTree.find(key);

        if (node == null) {
            System.out.println("The string does not exist");

        } else {
            System.out.println("Node "   node.stringData   " was found");
        }
    }

}

CodePudding user response：

The issue is inside insertNode(). Instead of comparing with root:

else if (key.compareTo(root.stringData) > 0) {
    node.rightChild = insertNode(node.rightChild, key);
}

you should compare with node:

else if (key.compareTo(node.stringData) > 0) {
    node.rightChild = insertNode(node.rightChild, key);
}