Need help understanind recussion in binary search tree

[senaddor]

Hello. I am having hard time understanding recussion in binary search tree. Assuming we have 6,4,7 in our tree the following inorder function should print 4,6,7 and I don't understand how it's done. Can somebody help explaining in more detail. Thank You.

void BinarySearchTree::print_inorder()
{
  inorder(root);
}

void BinarySearchTree::inorder(tree_node* p)
{
    if(p != NULL)
    {
        if(p->left) inorder(p->left);
        cout<<" "<<p->data<<" ";
        if(p->right) inorder(p->right);
    }
    else return;
}

[Narue]

>I don't understand how it's done.
The best way to understand recursion is to walk through a small example manually. Follow your code step by step with a pencil and paper, working on the logical tree you've already provided:

6
  /   \
4      7

root = 6, left link, recurse left
    root = 4, no left link, print, no right link, return
root = 6, print, right link, recurse right
    root = 7, no left link, print, no right link, return
root = 6, return

[senaddor]

Thank you for answering my question, but I have a folllow up question:

In the 2nd step

"root = 4, no left link, print, no right link, return"

how does program know not to go back thru left side again, but rather print 6 and go to right. Your answer is good, it's just I am not totally understanding what happens in background.

[senaddor]

I think I just figured it out, but you can feel free to correct me if I am wrong.

1) Originally on line 10 of code call was made to do left recursion
2) Left recursion was completed printing 4 and we return to line 11 of our code.

[Narue]

>1) Originally on line 10 of code call was made to do left recursion
>2) Left recursion was completed printing 4 and we return to line 11 of our code.
Bingo. There's nothing special about recursion, it's just a function call. You simply happen to be calling a function with the same body as the one making the call. It couldn't hurt to do some reading on stack frames and the mechanics of function calls to solidify your understanding.