Inorder of BT.

Hi,
I am having a hard time following the steps of the following recursion:

Code:

---

void inorder(Node * node) {
        if (node==NULL)
                return;
        inorder(node->left);
        printf("%d ",node->data);
        inorder(node->right);
}

---

Could anyone kindly explain this to me? For instance, why would 12 be printed right after 9 (please see attachment for data)?

Well you've got three choices.


// action
doLeft()
doRight()



doLeft()
// action
doRight()



doLeft()
doRight()
// action


Why not compare all three (pre-order, in-order and post-order) all at the same time?

I have. The recursion itself, the way it is processed, is giving me a hard time!
For instance, how would the program get to 12 after 9? 9->left is passed, it is NULL, then what happens? I have debugged it and still couldn't figure out the "leap" to 12.

Well there is no way down from 9, so the only way left is back up from where you came (ie, 12)

Quote:

---

Originally Posted by peripatein

I have. The recursion itself, the way it is processed, is giving me a hard time!
For instance, how would the program get to 12 after 9? 9->left is passed, it is NULL, then what happens? I have debugged it and still couldn't figure out the "leap" to 12.

---

It's not a leap, it's a return.

You start out at node 50, traverse left sequentially to nodes 17, 12, and 9.

9 has no left node, so it prints 9 and checks its right node. 9 has no right node so the function returns.

Now you're one level up the call stack, having just finished 12 left. The next thing that happens is to print 12 and then do 12 right.