Why is the root always null in this method insert method for binary tree

Question

Iam trying to implement a recursive insert node method for BST class

 public void insertNode(Node r, Node n)
{
    if(r == null)
    {
        System.out.println("r=n"+ n.data);
        r = n;
    }
    else
    {
        System.out.println("r=! null finding place in tree for "+ n.data);
        if(n.data <= r.data)
        {
            if(r.left == null)
                r.left = n;
            else
                insertNode(r.left, n);
        }
        else
        {
            if(r.right == null)
                r.right = n;
            else
                insertNode(r.right, n);
        }
    }
}

Im trying to invoke this method like so:

  int[] arrTree = {34, 2, 56, 12, 44, 39, 56, 1};
    BT t = new BT();
    for (int i = 0; i < arrTree.length; i++)
    {
        //System.out.println("Tree Root = "+ t.getRoot());
        BT.Node n =  t.new Node(arrTree[i]);
        t.insertNode(t.root, n);
    }

But Im always getting this output:

 r=n34
 r=n2
 r=n56
 r=n12
 r=n44
 r=n39
 r=n56
 r=n1

Node is an inner class of BT.

I cannot figure it out after hours of running and trying different things what Im doing wrong.

possible duplicate of [Is Java "pass-by-reference" or "pass-by-value"?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) — Bernhard Barker, Aug 18 '15 at 16:27

score 1 · Answer 1 · answered Nov 21 '13 at 13:33

1

Java is pass-by value language. In case of objects you pass the value of the reference, thus, creating new reference.

public void insertNode(Node r, Node n) {
    if(r == null) {
        r = n;
    }

Here you substitute the new reference to the root with the other reference; original reference to root (t.root) left unchanged.

To fix this issue you can get rid of the first parameter in the insertNode() method - the tree's root is the part of its implementation, so the tree already knows the reference to its root. Change all rs inside insertNode() to this.root.

answered Nov 21 '13 at 13:33

aga

27,954
13
86
121

Hi Thanks. But how can I use recursive method if I take away the r? – banditKing Nov 21 '13 at 14:35
The wording on this is slightly wrong. You pass the value of the reference, but the value of the reference doesn't permit you to reassign it. You don't create a new reference at all. – Makoto Aug 18 '15 at 16:07
@Makoto What would you say gets reassigned then? Because you are reassigning something. – Bernhard Barker Aug 18 '15 at 16:22

score 1 · Accepted Answer · answered Nov 21 '13 at 13:34

Judging by the code you've shown, my money's on the error being here:

public void insertNode(Node r, Node n)
{
    if(r == null)
    {
        System.out.println("r=n"+ n.data);
        r = n; //you overwrite the value of r but never use it
    }

Node r is actually a separate reference to whatever t.root refers to, so replacing r with another value won't change whatever t.root refers to outside the method. You can modify the referenced data inside a method, but not the reference itself.

score 0 · Answer 3 · answered Nov 21 '13 at 13:30

0

When you set r within the method, it does not affect the node that you pass in. So t.root is never set.

answered Nov 21 '13 at 13:30

arcy

12,845
12
58
103

Why is the root always null in this method insert method for binary tree

3 Answers3

Linked

Related