I don't understand recursion in binary search tree

[IHaveSmallBrain]

I have program that print the nodes of a BST in inOrder() traversal.

void inOrder(Node* root) 
{
    if (root != nullptr) 
    {
        inOrder(root->left);
        cout << root->data << " ";
        inOrder(root->right);
    }
}

Does it mean that the first recursion and the second recursion run at the same time? Or does the second recursion wait for the first to finish? I am very confused, can you guys help me understand this program. Thank you for your help

[AbstractionAnon]

Does it mean that the first recursion and the second recursion run at the same time?

No. There is no threading or other concurrency going on.

Or does the second recursion wait for the first to finish?

Follow the logic.

If the passed pointer is not null, Line 5: inOrder() is called with the left branch of the current node. The same logic is applied again, this time with the address of the second level left node. This continues until the left pointer is null. Let's say the second level left pointer is null, the code returns from the third level call, not having executed lines 5-7. The second level data item is then printed. inOrder() is called again with the right branch pointer and the logic walks down the right side of the tree until it finds the end of the branch (nullptr).

InOrder() calling it self is just like calling another function, except that you don't have to write a different function for every level of the tree.

BTW: IMO, root is a poor name for the argument. You only call inOrder() once with the true root of the tree. Every time after that you're calling inOrder() with a branch of the tree. node might have been clearer.

[seeplus]

Just for info. If you change the order of lines 5 - 7 you can also get pre-order (root, left, right) and post-order (left, right, root) traversals. Post-order traversal will produce a post-fix representation - which is heavily used in CS.

[kigar64551]

In C/C++ no code runs "at the same time" (in parallel) just by itself^*. If you call a function, then the calling function is "blocked" (suspended) at the point of the function call, and the called function runs in the very same thread as the calling function; the calling function will not be "resumed" until the called function returns.

Recursive functions, i.e. functions that call themselves, are no different in this regard!

If you want the called function to run "in parallel" to the calling function, i.e. if you want the function call to not be "blocking", then you have to start a separate thread, e.g. by using pthread or by using std::thread:
https://cplusplus.com/reference/thread/thread/
https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/pthreads.html

OpenMP is yet another option for parallel programming:
https://en.wikipedia.org/wiki/OpenMP

But be aware: Even if you create multiple threads (or processes), those will not really run "at the same time", at least not necessarily, but instead they will run in an "interleaved" fashion on the available CPU cores.


(*) as far as a single process is concerned, I mean; separate processes always run concurrently, of course!

[jonnin]

this is a good place for a visualization. You can trace the code, just treat the recursive calls like any other function call, and draw a picture that way (eg root, called with left node, called with that node's left node, printed, ... etc) or you can just look at one online, plenty of graphical examples and also tree drawing tools that let you see it in action.
consider: https://www.youtube.com/watch?v=4_UDUj1j1KQ

[Peter87]

AbstractionAnon wrote:

IMO, root is a poor name for the argument. You only call inOrder() once with the true root of the tree. Every time after that you're calling inOrder() with a branch of the tree. node might have been clearer.

The root of a tree is passed to the function. It doesn't matter if it's the root of a subtree or the whole tree. The function treats it the same anyway. Therefore I think "root" makes perfect sense.

[IHaveSmallBrain]

Thanks everyone !