How to add new node when building Binary Tree

Question

I'm working with an alternate version of the BinaryTree class called RedBlackTree. I'm trying to build the tree with this add method.

 public void Add(T val)
    {
        RedBlackNode<T> newNode = _rootNode;

        while(newNode != null)
        {
            if(val.CompareTo(newNode.Data) < 0)
            {
                newNode = newNode.LeftChild;
            }
            else if(val.CompareTo(newNode.Data) >= 0)
            {
                newNode = newNode.RightChild;
            }
        }
        newNode.Data = val;      //nullReferenceException thrown here  <---
        newNode.IsBlack = false;
        FixColors(newNode);
    }

_rootNode is a private field giving the root of the tree. It is initialized to null as given by specific instructions. This Add method is being called from within another class from a method that is reading in file info. On the first iteration, a nullReferenceException is thrown, I assume because the node I am trying to change is null. I don't know how else I am supposed to change the data value of these nodes. I will post the code to the rest of the program if necessary.

You need to check if _rootNode is null. If it is so, create a node using new keyword and assign it to _rootNode and exit this function — SomeUser, Nov 03 '15 at 01:10
@Partha why? Code can only reach that point when `newNode` is null. — Alexei Levenkov, Nov 03 '15 at 01:24
While I've considered this to be duplicate of [What is NRE and how to fix it](http://stackoverflow.com/questions/4660142/what-is-a-nullreferenceexception-and-how-do-i-fix-it) in reality this is different question as OP explicitly finds null - so problem is not NRE, but rather the way how searching stops. — Alexei Levenkov, Nov 03 '15 at 01:32
@OP I don't understand how the answer you've accepted could solve your problem. If you only make the change described in that answer, `newNode` is still guaranteed to be null at the end of the loop, and will result in the NullReferenceException you were describing earlier. — Asad Saeeduddin, Nov 03 '15 at 01:41
Actually it didn't solve my answer. I thought it would at first glance, but I'm still working on it. Your answer is another step in the right direction, although the instructions I am given also say that I am supposed to loop while the node != null. I'm still having issues implementing it that way without getting a nullReferenceException. — Lance_P, Nov 03 '15 at 02:06

Asad Saeeduddin · Accepted Answer · 2015-11-03T01:51:48.880

0

Well, the while loop isn't going to exit while newNode isn't null. That implies newNode is going to be null once the loop exits. I think what you want is to create a new node if the RightChild or LeftChild nodes is null, and set newNode to that.

In addition, as Partha's answer points out, you need to initialize the _rootNode value if it isn't already set.

I don't really know how the parent property of the node is set, so I'm going to assume the parent node is injected as a constructor argument of the child node:

public void Add(T val)
{
    RedBlackNode<T> parent = _rootNode;
    RedBlackNode<T> target = null;

    while(target == null)
    {
        if(val.CompareTo(parent.Data) < 0)
        {
            if (parent.LeftChild == null) 
                target = parent.LeftChild = new RedBlackNode<T>(parent);
            else
                parent = parent.LeftChild;
        }
        else if(val.CompareTo(newNode.Data) >= 0)
        {
            if (parent.RightChild == null) 
                target = parent.RightChild = new RedBlackNode<T>(parent);
            else
                parent = parent.RightChild;
        }
    }
    target.Data = val;
    target.IsBlack = false;
    FixColors(newNode);
}

edited Nov 03 '15 at 01:51

answered Nov 03 '15 at 01:13

Asad Saeeduddin

46,193
6
90
139

Need 1/2 upvote to each answer as for some reason only half of solution provided (but combined one would be correct). – Alexei Levenkov Nov 03 '15 at 01:35
@AlexeiLevenkov I don't really understand what's going on in the other answer. Could you explain what I'm missing? I thought `_rootNode` was a property of whatever class contains this method (and as such it would be unlikely for `Add` to have to initialize it). – Asad Saeeduddin Nov 03 '15 at 01:37
@AlexeiLevenkov In fact, the `_` prefixed member name convention is usually for readonly fields, so it isn't even clear you *can* change `_rootNode` in the method. – Asad Saeeduddin Nov 03 '15 at 01:38
According to the question: "_rootNode is a private field giving the root of the tree. It is initialized to null as given by specific instructions" - so initializing it to something likely responsibility of `Add` for given assignment. Side note: I'd not make *any* assumptions based on variable names for homework questions - copy-paste creates varying names with no relation to scope/static/readonlyness :) – Alexei Levenkov Nov 03 '15 at 01:41
@AlexeiLevenkov Ah, right. I didn't even read that bit. EDIT: nvm, I understand how it could be null – Asad Saeeduddin Nov 03 '15 at 01:44
homework is not expected to be logical - it generally designed to test particular piece of recently acquired knowledge about topic... – Alexei Levenkov Nov 03 '15 at 01:47
Alright, with a combination of your answers, I was able to follow the instructions given to me and still avoid the exception. This was my first question posted on this site and a great first impression. I will be sure to come here again if I have issues. Thank you everyone. – Lance_P Nov 03 '15 at 02:23

score 0 · Answer 2 · answered Nov 03 '15 at 01:14

You need to create the node before you access the other fields. So if _rootNode is empty you create using new keyword.

public void Add(T val)
{
      if(_rootNode == null)
      {
           RedBlackNode<T> newNode = new RedBlackNode<T>();
           newNode.Data = val;
           newNode.IsBlack = false;
           _rootNode = newNode;
           return;
      }
      //Followed by your logic
}

How to add new node when building Binary Tree

2 Answers2