Maximum PC

We've just finished going over binary trees in my computer science class and I understand most of it (conceptually, implementing a binary tree may be a different story ). However, I do not fully understand exactly how a traversal works recursively.

My teacher provided this pseudo-code for explaining traversal:

What I'm trying to figure out is how it hits every single node in the binary tree with this recursive call. I can see that it would head to the left, recursively, but at what point in the traversal algorithm does it stop going to the left and start going right from the sub-tree's root?

We start with the furthest item to the right and head left. When we reach the end, the program does something to the sub-tree root and heads to the right.
Read this: Wikipedia on Traversal
Your teacher's example is the first under this heading.
Think of it in a DOS prompt:

So, ".." is the root of the sub-tree C. To traverse, we go to the right and look at Programs, then Users, then Windows. In a binary tree, you have stuff on both sides of the root, so we first go to the left of the root, then do the action. Next, we go to the root, and scan to the right.

It helps if you draw a tree and work through it using the recursive algorithm.

Imagine a tree with 3 levels. The first level has only the root (0) . The second level has two nodes (1 and 2) . The third level has four (3, 4, 5 and 6).

0
1 2
3 4 5 6

(sorry .. this diagram isn't working well .. these should be spaced out in a pyramid. 0 branches to 1 and 2 ... 1 branches to 3 and 4 ... 2 branches to 5 and 6)


Start at the root:
traverse ( 0 )
root is not null, so we traverse (root -> left) to 1.
1 is not null, so we traverse (1 -> left) to 3.
3 is not null, so we traverse (3 -> left) to null.
null is null, so we do nothing and return.
do something with 3
traverse (3 -> right) to null.
null is null so we do nothing and return.
do something with 1
traverse (1 -> right) to 4
4 is not null, so we traverse (4 -> left) to null
null is null, so we do nothing and return.
do something with 4
traverse (4 -> right) to null.
null is null so we do nothing and return.

... and so on.

Does that make sense?



He understands traversals. He is having difficulty with recursion.

Still, pretty good considering the programming class I had only spent 10 minutes on the subject.

Well, no, because you just paraphrased the wiki entry rather than addressing his question.

I wrote the thing before I looked up on Wikipedia to double check. I then incorporated the link.

Well, he hasn't come back here so I guess the point is moot.