Java – Binary Tree pointer still null after initialization?



This question is very abstract and thus very hard to describe or search for, thus why I am here. It’s a very simple question however.

I have the following class:

class Node<T>
{
    Comparable data;
    Node<T> left, right;

    public Node(Comparable data)
    {
        this.data = data;   
    }
}

What happens if I have:

/*
* Imagine this root looks like the following:
*       10 (root)
*       /       
    null        null
*/
Node root;

// Imagine we are inside of the insert method and this
// is the current value that is going to be inserted.
int valueIAmTryingToInsert = 5;

// As we see from the tree above, "child" WILL be null.
Node child = (valueIAmTryingToInsert.compareTo(root.data) < 0 ? root.left : root.right);

if (child == null)
{
    child = new Node(data);
    return true;    
}

// Recursive statement would happen here.

Notice that child is a pointer that points to either the left or the right child of root. BUT, what happens if I instantiate the Node that child is pointing to? After calling child = new Node(data);, does the tree currently look like:

    10 (root)
    /       
    5       null

If It doesn’t look like that, explain why. Because my understanding is even though Node child is null, the pointer is still pointing to one of root‘s children. I am pretty sure this doesn’t work, as my editor underlines child in the statement child = new Node(data); and claims The value new Node(data) assigned to 'child' is never used (even though it is being used).

Answer

You are never assigning it to the root node as its “left”.

In plain English this is what your code does:

-Is the left (or right) of the root null? -Yes -Create a new node please.

But there’s no association between this new Node and the root Node. You might need something like this:

Node root;
Node child;
Integer valueIAmTryingToInsert = 5;
if(valueIAmTryingToInsert.compareTo(root.data) < 0){
    if(root.left == null){
        root.left = new Node(valueIAmTryingToInsert);
    }
    child = root.left;
}else{
    if(root.right == null){
        root.right = new Node(valueIAmTryingToInsert);
    }
    child = root.right;
}
return true;    

EDIT: This code is just an example, but if root.data is null you’ll get a NullPointerException because of the comparision. That’s something you might be aware and take care of.

EDIT 2: I can see you’re still confused and the main issue is that you have to keep in mind that null is not a reference to an object. It is a “mark” that indicates that the object has not been yet initialized. So when I say a = null; b = a is not like a and b are pointing to the same object (Because nullis not a valid object or reference), it means they both have not yet been initialized. They are separate independent variables. Then when I initialize one a = new MyClass() I’m asking for a memory reference for a, but b remains pointing to nowhere in memory.

See null as a way of telling “This object is pointing to nowhere”. If things were as you are thinking (If I initialize a then b should point there too); then every single null object in the program should point to where a is now pointing to.



Source: stackoverflow