CODEWITHSUNDEEP
c++
user3525627
user3525627

Reputation: 19

Binary search tree recursive display function, not sure how it works?

I have a BST and I found this function online, which prints it in the correct order, but I don't understand how.

void display()
{
    inOrder(root);
}
void inOrder(treeNode* n)
{
   classA foo;
   if (n != NULL)
   {
        inOrder(n->left);
        foo = *n->item;
        cout << foo << endl << endl;
        inOrder(n->right);
    }
 }

I initialize each node's left and right to NULL. Why does the if statement continue after a NULL pointer is sent in, and where does it continue from?

Upvotes: 0

Views: 94

Answers (1)

R Sahu
R Sahu

Reputation: 206607

Say you have the following BST:

enter image description here

When inOrder is called with this BST,

Recursion level 0

n points to 8. So you enter the block:

    inOrder(n->left);
    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

inOrder is called using n->left as argument, which is node 3.

Recursion level 1

n points to 3. So you enter the same code block.

inOrder is called using n->left as argument, which is node 1.

Recursion level 2

n points to 1. So you enter the same code block.

inOrder is called using n->left as argument, which is NULL.

Recursion level 3

n points to NULL. So you do not enter the above code block. You simply return from the function. Now are back in the next statement in the previous recursion level.

Recursion level 2

The following lines are executed:

    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

You print 1. Then, inOrder is called using n->right as argument, which is NULL.

Recursion level 3

n points to NULL. So you do not enter the above code block. You simply return from the function. Now are back in the next statement in the previous recursion level.

Recursion level 2

There are no more lines to execute. The function simply returns to previous recursion level.

Recursion level 1

The following lines are executed:

    foo = *n->item;
    cout << foo << endl << endl;
    inOrder(n->right);

You print 3. Then, inOrder is called using n->right as argument, which is node 6.

You can now follow this step by step all the way. The end result is that you will end up printing the numbers in the following order.

1
3
4
6
7
8
10
13
14

Upvotes: 2

Related Questions