0

I created a program which stores key/value pairs into a Binary Search Tree. The class contains a root pointer which keeps track of the root node of the tree. This.root is set to null in the constructor.

The following method put(K, V) attempts to insert a new key/value pair into the tree. If the key already exists in the tree, the method returns the existing value corresponding to that key. If not, the key/value pair is inserted through the helper method put(K, V, BNode). ***Usually I would just return this.put(...), but in this code snippet I replaced it with return null so that I may add a print statement before it to check whether the root node was actually modified

My program fails at inserting the first key/value pair. I placed print statements in my insert and put methods to check if they work properly. In this case, curr (which was just this.root) is null before the insertion, as expected since we're starting with an empty tree. I create a new node, and call return this node in insert(). Now curr points to this created node. The print statement "curr key" + curr.key prints out the correct key, suggesting that this node creation worked. But I get a NullPointerException when I try to print this.root.key. Shouldnt modification of curr in the second method have also modified this.root in the first method?

//this.root is the root node of this binary search tree
public V put(K key, V val) {
    System.out.println("put reached");
    this.put(key, val, this.root); // original return statement
    System.out.println("root key: " + this.root.key); // checks if root node was modified
// THIS print statement returns a NullPointerException

    return null; // dummy return statement
}

private V put(K key, V val, BNode curr) {
    V originalValue = this.get(key, curr); // returns null if key does not exist
//else returns corresponding key value

    if (originalValue == null) {
        curr = this.insert(key, val, curr); // helper method which uses recursion to insert 
        System.out.println("curr key " + curr.key); // checks if curr was modified
        this.size++;
        this.state++;
    }

    return originalValue;
}

private BNode insert(K newKey, V newValue, BNode n) {
    if (n == null) {
        return new BNode(newKey, newValue); 
    } else if (newKey.compareTo(n.key) < 0) {
        n.left = this.insert(newKey, newValue, n.left);
    } else {
        n.right = this.insert(newKey, newValue, n.right);
    }

    return n;
}
goldrik
  • 115
  • 6

2 Answers2

0

Shouldnt modification of curr in the second method have also modified this.root in the first method?

Short answer: No. This is because the value of root is never changed.

This should help clear things up, and explains why this happens better than i can: Is Java "pass-by-reference" or "pass-by-value"?.

In short if you want to assign a new node as root you need to do it explicitly and not by trying to change the value passed to the method since that will only change what curr is pointing at.

Community
  • 1
  • 1
trappski
  • 1,066
  • 10
  • 22
0

Thanks for the quick reply trappski

If Java really is pass by reference then the issues I've been having with my program make more sense now. But why is it that a recursive method such as this one works if only a duplicate BNode is being modified, instead of the original one that is part of the tree?

private BNode deleteMin(BNode n) {
    if (n.left == null) {
        return n.right;
    }

    n.left = this.deleteMin(n.left);
    return n;
}
goldrik
  • 115
  • 6
  • Here you operate on methods on the object instead of modifying the reference-value that was passed. – trappski Mar 30 '16 at 05:18