Parameter assignment not working as expected

Question

I am working with binary search tree for class assignment. I'm trying to replace a node with a different node by assigning the new node to the recursive method parameter.

The line node = minNode(node.right); is not working as expected. It does modify the parameter SearchTreeNode<E> node but this change doesn't propagate to this.overallRoot. For example, if the root of the tree is 5, and we remove 5, and the substitute would be 7, this.overallRoot remains 5 even though the parameter node has been changed to 7. See screenshots below.

Any idea what I'm doing wrong?

public void remove(E data) {
    if (this.overallRoot != null) {
        this.removeData(this.overallRoot, data);
    }
}

private void removeData(SearchTreeNode<E> node, E data) {
    if (node.data == data) {
        if (node.left == null && node.right == null) {
            node = null;
        } else if (node.left != null && node.right != null) {
            node = minNode(node.right);
        } else if (node.right == null) {
            node = node.left;
        } else if (node.left == null) {
            node = node.right;
        }
    } else if (data.compareTo(node.data) < 0) {
        this.removeData(node.left, data);
    } else if (data.compareTo(node.data) > 0) {
        this.removeData(node.right, data);
    }
}

private SearchTreeNode<E> minNode(SearchTreeNode<E> node) {
    if (node.left == null) {
        return node;
    }
    return minNode(node.left);
}

Answer 1

Your diagnosis is exactly right: modifying node doesn't do any good because node is a local variable. Modifications to parameters don't propagate to the caller.

You can modify node.left and node.right, though. Those changes would be visible. You'd need to restructure your code to take advantage of that. It's not a quick fix.

Alternatively, you could return a value to removeData's caller and have the caller change the appropriate variable. That, too, would take some thinking to figure out what to return from each of removeData's branches. Calling it would look like:

node.left = this.removeData(node.left, data);