Adding node to tree - Why is the root not getting initialized?

Question

I have written two functions for adding a new node to a tree: one public and one private. The private one is recursive. The public one calls the recursive one. First question: Is this acceptable practice?

public void addNode(int val) {
    addNode(val, root, null, 0);
    System.out.println("Root is null: " + (root == null));
}

private void addNode(int val, Node node, Node parent,int height) { 
    
    if(node == null) {
        node = new Node(val, height, 0);
        System.out.println("is new node equal to root?"+(node == root));
        System.out.println("Added node on height: " + node.getHeight());
        return;
    }
        height++;
        addNode(val, node.left, node, height);
        addNode(val, node.right, node, height);

}

Now here is the problem: The root variable does not get initialized. It is declared in the tree class. public Node root;

This is very confusing to me since I am aware that Java is pass-by-reference, not pass-by-value. Why is root null after these functions have been called?

Console output:

is new node equal to root?false
Added node on height: 0
Root is null: true

Answer 1

If in Java code a function assigns a new value to a function parameter, this never impacts the variable that the caller may have passed as argument. You may have been confused with what happens when a parameter variable is mutated: for instance, if it is an object and you assign a different value to one of its properties, then this change is visible to the caller's object, since it really is the same object. But a plain assignment to a parameter will always have an effect on that local variable only.

To make it work, design your function to return the node that you provided to it (whether it got a new value or not).

There is another issue: you are currently adding a new node in both the left and right subtree (if they exist), and this repeats recursively. I will assume you were trying to insert values in a binary search tree, and so you should choose in which subtree you will add the node.

Finally, it is not needed to pass parentNode or height as argument, since you seem to store the height in each node, and so you know that the new node's height must be one more than the height stored in its parent node (or, when absent, 0).

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

private void addNode(int val, Node node) { 
    if (node == null) {
        return new Node(val, 0, 0);  // NB: height will be updated when backtracking
    }
    if (val < node.val) {
       node.left = addNode(val, node.left);
       node.left.height = node.height + 1;
    } else {
       node.right = addNode(val, node.right);
       node.right.height = node.height + 1;
    }
    return node;
}

Finally, the name "height" is a bit misleading here, as this term is supposed to denote the height of the (sub)tree of which the node is the root. But height in this code represents the depth of the node in the tree. See What is the difference between tree depth and height?.