Binary Tree insert root always null

Question

I tried to write a recursive function for adding Nodes into a Binary Tree.
The Problem is that although the root has a new value after inserting the first element
(confirmed by System.out.println() ), it´s still null when I try to get the root value in the main through System.out.println();

package polo;

public class BTNode {
    public int value;
    public BTNode left;
    public BTNode right;

    BTNode(int value){
        this.value = value;
        left = null;
        right = null;
    }
}

package polo;

public class Tree {
public BTNode root;

    public Tree() {
        root = null;
    }

    public void add(int i, BTNode n) {
        if (n == null) {
            n =  new BTNode(i);
            System.out.println("New root value : " + n.value);
        } else {
            if (i < n.value) {
                if (n.left == null) {
                    n.left =  new BTNode(i);
                } else {
                    add(i, n.left);
                }
            } else { // i >= n.value
                if (n.right == null) {
                    n.right =  new BTNode(i);
                } else {
                    add(i, n.right);
                }
            }
        }
    }

    public static void main(String[] args) {
        Tree t = new Tree();
        t.add(3, t.root);

        System.out.println(t.root.value);
    }
}

The command line output is :

New root value : 3

Exception in thread "main" java.lang.NullPointerException at polo.Tree.main(Tree.java:57)

(Line 57 is where System.out.println(t.root.value); stands)

Sorry but I don´t understand your comment. The root is null when there is no Element but after inserting a new one (root = new Node()) it should not be null ? — Oskar M, Aug 18 '15 at 16:05
@HovercraftFullOfEels It's not common sense if you don't understand how Java passes parameters to functions (there is a `n = ...` which may appear to change `root`). — Bernhard Barker, Aug 18 '15 at 16:08
As an aside: develop this tree in such a way that the caller only ever passes the value they want to add to it. Don't let them know anything about the internal node structure. — Makoto, Aug 18 '15 at 16:08
@HovercraftFullOfEels `root` gets passed to `add` as `n`, which is then reassigned. In Java, this would work if you modify it, but not if you reassign it. Without a firm understanding of how Java works, this difference may not make sense. As least that's my point of view. — Bernhard Barker, Aug 18 '15 at 16:15
I stand corrected, my apologies to all as I did not see his trying pass in root as a method parameter. — Hovercraft Full Of Eels, Aug 18 '15 at 16:16
Relevant reading - [Is Java “pass-by-reference” or “pass-by-value”?](http://stackoverflow.com/questions/40480/is-java-pass-by-reference-or-pass-by-value) (indirectly answers your question) — Bernhard Barker, Aug 18 '15 at 16:23

score 2 · Accepted Answer · answered Aug 18 '15 at 16:06

2

Java has references, but not references to references.

When you have

public void add(int i, BTNode n) {
    if (n == null) {
        n =  new BTNode(i); // alters the local variable n only.

Basically add doesn't alter t.root. Instead you should not pass root at all and have the add method handle it.

public void add(int i) {
    if (root == null) {
        root = new BTNode(i);
    } else {
        root.add(i);
    }
}

answered Aug 18 '15 at 16:06

Peter Lawrey

525,659
79
751
1,130

I have run into OP's problem before and now I am wondering if there is a language that has references to references? And I am wondering if a language could handle this problem, would it be more useful than confusing? – under_the_sea_salad Aug 18 '15 at 16:14
Thank you for your friendly answer. This solved my problem. – Oskar M Aug 18 '15 at 16:16
1

@bourbaki4481472 C/C++ has `&&n` and `*&n` and `&*n` and `**n` as well as pointers to pointers to pointers which can be useful in some data structures. (very rarely) – Peter Lawrey Aug 18 '15 at 16:24

Binary Tree insert root always null

1 Answers1