How are if statements are excuted in a function?

Question

I stumbled across an interesting case that makes me question what I know about if statements.

I have this code for insertion for binary trees:

void insert(Node<T>* &currentNode, const T& x)
    {
        if (currentNode == nullptr)   
        {                               
            currentNode = new Node<T>(x);
        }

        if (x >= binTree<T>::root->data)
        {
            insert(currentNode->right, x);
        }
        else if (x < binTree<T>::root->data) 
        {
            insert(currentNode->left, x);
        }

    }

The problem I was facing was that whenever I called this function to insert into the tree, it gave me a segmentation fault, after running valgrind, it told me that a stack overflow error occurred. I tested to see if the first if block was causing the problem by writing a cout statement and lo and behold my cout statement was excuted infinitely many times.

However, after changing that second if block to one single unified if statement like this:

if {}
else if {}
else if {}

The code worked perfectly and was not stuck in an infinite loop. How does one explain this behavior? Doesn't the if statement just test the condition and if it is false it continues on the rest of the block?

Answer 1

Not expecting any credit for this answer since it's coming in late, but wanted to add another perspective. The problem here is that you've created (intentionally or not) a recursive function without a base case (which equals stack overflow).

It's guaranteed that one of the following statements will be true:

if (x >= binTree<T>::root->data)
{
    insert(currentNode->right, x);
}
else if (x < binTree<T>::root->data) //could just as well have been only "else"
{
    insert(currentNode->left, x);
}

By implementing the solution you found and which @David Schwartz confirmed, you're essentially converting the if (currentNode == nullptr) block into the base case, which solves the problem.

Answer 2

It should be quite obvious.

Without the else, each call to insert always makes at least one more call to insert, leading to an infinite number of calls. The second if is always executed, and either way it calls insert.

With the else, it is possible for insert not to call insert -- if currentNode is null.