Week 6: Trees

I've never been a morning person. Especially not on Mondays. But, ever since I switched to Comp. Sci., the life of returning to the lecture hall every Monday morning wasn't the same anymore.

But I digress...

Back on Monday, Dan covered tree terminologies, tree traversal, then followed up with code implementation the rest of the week. The tree terminologies seem simple enough. "Parent" and "siblings" makes sense to about anyone. But, the tree traversals aren't as simple as it looks.

On page 11 of week 6's slides, it says:

"Preorder: Visit the root node, do a preorder traversal of the
 left subtree, and do a preorder traversal of the right subtree

Inorder: Do an inorder traversal of the left subtree, visit the
root node, and then do an inorder traversal of the right
subtree

Postorder: do a postorder traversal of the left subtree, do a
postorder traversal of the right subtree, and visit the root node"

I thought I understood tree traversal after reading these three definitions, but once we got to the actual example, the inorder traversal was far from what I expected.

After a simple Google search, I found a website with a more detailed example and explanation for a CS beginner like me.

Here's the link: http://datastructuresnotes.blogspot.ca/2009/02/binary-tree-traversal-preorder-inorder.html

(This is a picture from the same website.)

The Inorder traversal is done recursively. Here's how the author of that blog explained it:

"(i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10"
It cleared my concept quite a lot, as I originally thought you start with the left subtree and just enumerate each level is an ascending order, then visit the root, and visit the right subtree eventually. This is wrong. But, to further illustrate my wrong concept, here's an example of what my method would create using the above figure: 1, 0, 3, 2, 5, 4, 6, 7, 9, 8, 10.

Of course, don't do that!

That's all for the week. Thanks!