Binary Search Tree Insertion Method in Java

Question

In the following insert method for a binary search tree (BST), the left side of the tree is being updated correctly, but there is an issue with inserting values on the right side. Despite using the debugger to check the output, the method adds some values incorrectly to both the left and right sides. Can someone help identify and fix the issue? This got me confused as it is my first time exercise on a binary search tree question

//here is the code

public void insert(int number) {
        Node newNode = new Node(number);
        if (isEmpty()) {
            root = newNode;
        }
        Node current = root;
        Node parent;
        while (true) {
            parent = current;
            if (current.data > number) {
                current = current.left;
                if (current == null){
                    parent.left = newNode;
                    return;
                }
            }
            else{
                current = current.right;
                if(current == null){
                    parent.right = newNode;
                    return;
                }
            }
        }
    }

Answer 1

There are two points that need to be edited in the code block.

• End Process If Tree is Empty: After the isEmpty() check, if the tree is empty, I added return statement after setting the new node as root. This prevents unnecessary looping.

• Initializing the Parent Variable: Before the loop, I initialized the parent variable to null. This is important to ensure that the parent and current variables are updated correctly within the loop.

    public void insert(int number) {
        Node newNode = new Node(number);
  
        if (isEmpty()) {
            root = newNode;
            return; // End Process If Tree is Empty.
        }
  
        Node current = root;
        Node parent = null; // Initializing the Parent Variable
  
        while (true) {
            parent = current;
            if (current.data > number) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
  

Hope it was useful.