Help Understanding this code sample

[KittyIchigo1]

I saw this on Stack Overflow and wanted to understand it a bit more.

  void Tree::insert(int data)
{
    if(!root)
    {
         root = new Node(data);  // Node constructor should receive
                                 // the data value and init internal value from it
                                 // it should also set left and right pointers to 0
         return;
    }

    Node* insertIterator = root;
    Node* parent = 0;

    while(insertIterator)
    {
         parent = insertIterator;
         insertIterator = data < insertIterator->getData() 
             ? insertIterator->getLeft()
             : insertIterator->getRight();
    }

    if(data < parent->getData())
         parent->setLeft( new Node(data) );
    else
         parent->setRight( new Node(data) );
}

This code is for iteratively inserting nodes into a binary tree.
I don't really understand why parent is being set to 0 - I don't get what parent is really doing in the first place. Nor do I understand the while loop section.

My thoughts so far have been:
Parent is supposed to be the 'iterator' (like how 'i' is in a for loop?) But then I don't understand how it's being updated.
For the while loop: while at root, check if the data that wants to be inserted is less than the data at root. If it is, set it to the left, and if it's not set it to the right?

I'm just confused and I would appreciate if someone could help me break this dowwn.

[dutch]

insertIterator is moving down through the tree until it finally becomes null. parent saves insertIterator's previous value, which will become the parent of the new node.

Alternatively you can use a double pointer:

void Tree::insert(int data) {
    Node** node = &root;
    while (*node)
        node = data < (*node)->data ? &(*node)->left : &(*node)->right;
    *node = new Node(data);
}

[coder777]

The parent is kept so that line 23/25 can be processed. Actually you need something to add the node to.

The loop finds the most appropriate branch to add the data to. When the data is smaller than left -> go left otherwise right. It does so until no element is available (insertIterator is nullptr). Then the parent comes into play. It is the last element available and the data is added to it depending on whether it's smaller or not.

[keskiverto]

Node* insertIterator = root;
Node* parent = 0;

I don't really understand why parent is being set to 0

It is a good habit to initialize variables with known values.

    Node* insertIterator = root;
    Node* parent; // uninitialized

    while(insertIterator) // what if this is false?
    {
        // ...
    }

    if ( data < parent->getData() )

A compiler could warn that the if-statement uses uninitialized parent. Of course in this program the previous if-statement already ensures that it will not happen, but compiler might not be that smart.

One should pay attention to compiler warnings. The initialization removes one warning that we know to not be an issue.


Initializing a pointer with value 0 is less common.

Node* parent = 0; // implictly converts 0 to null pointer value
Node* parent = NULL; // preprocessor macro for null pointer value
Node* parent {}; // zero initialization. Since C++11
Node* parent = nullptr; // Since C++11 

See https://en.cppreference.com/w/cpp/language/pointer#Null_pointers

[KittyIchigo1]

while(insertIterator)
    {
         parent = insertIterator;
         insertIterator = data < insertIterator->getData() 
             ? insertIterator->getLeft()
             : insertIterator->getRight();
    }

That makes a lot more sense, thank you very much.

For the line insertIterator = data < insertIterator->getData() , why wouldn't it give an error? insertIterator is a node*, but data <insertIterator->getData() is a boolean value.

[KittyIchigo1]

Nevermind, I've figured it out...it has to do with the ?: operator. Thank you all so much for the help.