Issues with binary search tree

Question

I need some help to why an insertion in a bst doesn't work on the following code. Is there some concept on how java passes parameters that I do not know?

 public void insert(int input){
        insert(root, input);
}
private void insert(Node node, int input){
    Node new_node = new Node(input);
    if (node == null) {
        node = new_node;
        }
    else if (input == node.data) {
        System.out.println("input exists");
        }
    else {
        if (input < node.data) {
            insert(node.left, input);
        }
        else{
            insert(node.right, input);
        }
    }
}

The parameter `Node node` is a local variable. Reassigning that won't have an effect. Java is call by value. — f1sh, Jul 28 '20 at 11:31
also you're assigning a value to null, it's like a floating node, not attached to anything. — maha, Jul 28 '20 at 11:32

0xh3xa · Answer 1 · 2020-07-28T11:42:10.200

Try to insert like this in the BST

    public void insert(int val) {
        root = put(root, val);
    }

    private Node insert(Node node, int val) {
        if (node == null)
            return new Node(val);
        int cmp = Integer.valueOf(val).compareTo(node.data);
        if (cmp < 0)
            node.left = insert(node.left, val);
        else if (cmp > 0)
            node.right = insert(node.right, val);
        else
            node.data = val;
        return node;
    }

score 0 · Accepted Answer · answered Jul 28 '20 at 11:40

Reassigning the parameter node won't change anything about the thing you passed to the method (node.left or node.right):

node = new_node;

Because node stores a reference to the Node object (that you want to replace). The assignment only changes the reference so that it refers to another object. See this for more info.

You could reassign node.left and node.right instead:

Node new_node = new Node(input);
if (input == node.data) {
    System.out.println("input exists");
} else if (input < node.data) {
    if (node.left != null) {
        insert(node.left, input);
    } else {
        node.left = new_node;
    }
}
else{
    if (node.right != null) {
        insert(node.right, input);
    } else {
        node.right = new_node;
    }
}

Thank you, this really helped – alexolakpe Jul 28 '20 at 14:17 — alexolakpe, Jul 28 '20 at 14:17

Issues with binary search tree

2 Answers2