Whats wrong in this BST implementation?

Question

Why am I getting false while doing search(7)? I tried recursive solution its working fine.. tried implementing with loop failed

public class BST {

    class Node {
        int data;
        Node left , right;

        public Node(int data) {
            this.data = data;
            this.left = this.right = null;
        }
    }

    Node root;

    public BST() {
        this.root = null;
    }

    public void insert(int data) {
        // create a new node and start iteration from root node
        Node newNode = new Node(data);
        Node currentNode = this.root;

        while (true) {
            if (currentNode == null) {
                currentNode = newNode;
                break;
            }

            if (data < currentNode.data) { // if data is less go left
                currentNode = currentNode.left;
            } else if (data > currentNode.data) {   // if data is greater go right
                currentNode = currentNode.right;
            } else {    // do nothing for duplicates
                break;
            }
        }
    }

    public boolean search(int data) {
        Node currentNode = this.root;

        while (true) {
            if (currentNode == null) {
                return false;
            }

            if (data == currentNode.data) {
                return true;
            } else if (data < currentNode.data) {
                currentNode = currentNode.left;
            } else {
                currentNode = currentNode.right;
            }
        }
    }

    public static void main(String... args) {
        BST tree = new BST();

        tree.insert(15);
        tree.insert(7);

        System.out.println(tree.search(7));
    }
}

Answer 1

Problem is inside the insert method - you are not inserting the nodes correctly inside the tree.

1. If the tree is empty, you should assign to this.root, not currentNode. Assigning to currentNode has no affect on this.root.

   Currently, your code isn't inserting any node inside the tree; it simply assigns the new node to the local variable of insert method, i.e. currentNode.

2. If the condition data < currentNode.data is true, then you need to check if the currentNode.left is null or not. If it is, then link the new node with the current node as shown below:

   currentNode.left = newNode; 
   

   If currentNode.left is not null, then do the following:

   currentNode = currentNode.left;
   

   Currently, your code moves the currentNode to null and then assigns the newNode to the currentNode without a reference to its parent node in the tree.

3. Do step 2 for data > currentNode.data as well.

Change the implementation of the insert method as shown below:

public void insert(int data) {

    Node newNode = new Node(data);
    
    if (this.root == null) {
        this.root = newNode;
        return;
    }
    
    Node currentNode = this.root;

    while (true) {
        if (data < currentNode.data) {
            if (currentNode.left == null) {
                currentNode.left = newNode;
            } else {
                currentNode = currentNode.left;
            }
        } else if (data > currentNode.data) {
            if (currentNode.right == null) {
                currentNode.right = newNode;
            } else {
                currentNode = currentNode.right;
            }
        } else {
            break;
        }
    }
}