Logout

5.1.16

State the result of inorder, postorder and preorder tree traversal.

 

Teaching Note:

 

Sample Question:


From Sample Paper 1 2014:

sample paper question on binary trees

 

JSR Notes:

Inorder, postorder and pre order are the three main ways to traverse a binary tree. The idea is that we want to "traverse" the tree, thereby going to each and every node. And the question is how will we do so? We cannot just "start at the beginning" and "go to the end", as we would be able to do with an array or with a list. It's more difficult to figure out how to traverse because each node (except for the end leafs) has two ways you can go. An iterative solution does not lend itself, but a recursive one does: at each node, visit its children a certain way.

To remember which order is which, "pre" and "post" refer to the order in the sequence when the node itself is dealt with.

And left is before right.

 

So with pre-order, we:
- visit the node itself
- visit the left node
- visit the right node

With in-order, we:
- visit the left node
- visit the node itself
- visit the right node

And with post-order, we
- visit the left node
- visit the right node
- visit the node itself

This may be, in fact all that is required for this assessment statement: to state the order in which one or all of the traversals operate. But a more sophisticated question would be to trace the traversal of an actual tree...

... but just in case actual traversals are required here, here are videos showing how to do your trace for each. More on this in the OOP option notes, in which such traces will be required. Furthermore, here's the detailed animation of one of them, as linked on 5.3.3

2212 animation of Binary Tree traversal trace

And here's another VERY GOOD video, and I like the way the guy adds "V" for value, or "R" for Right, and "L" for Left when as each of those things is done. So watch it first, and pretend I did that too, below, rather than just saying it.

Loading the player...

Pre-order Traversal



Loading the player...

In-order Traversal



Loading the player...

Post-order Traversal