0

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
Hannes Elfving
  • 41
  • 6

2 Answers2

0

Of course there is nothing wrong in calling private method (even recursive) from public method. Root is null simply because you are assigning new value to node argument, you are not changing object, but you are creating new one.

following

private void addNode(int val, Node node, Node parent,int height) {
   ...
   node = new Node(val, height, 0);

will not change argument node in caller. So after calling

addNode(val, root, null, 0);

root stays unchanged (with null value)

Also keep in mind objects are passed by value in Java.

Actually (inside Java) in function you receive only memory address (value) for node (e.g. 000000D5098FFA70 in x64 arch). So if you modify e.g. node.left you are actually changing memory at address 000000D5098FFA70 + 4. However if you change that address - value - you lose access to this object. And from that moment you are working only with local variable. This is why it is called passed by value.

Michal Drozd
  • 1,311
  • 5
  • 13
  • 26
0

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?.

trincot
  • 317,000
  • 35
  • 244
  • 286