Tree traversal algorithms for a binary tree
For the tree above a tree traversal can be performed in 3 different ways.
Contents
Preorder[edit]
The first type of traversal is preorder whose code looks like the following:
sub P(TreeNode)
Output(TreeNode.value)
If LeftPointer(TreeNode) != NULL Then
P(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
P(TreeNode.RightNode)
end sub
This can be summed up as
 Visit the root node (generally output this)
 Traverse to left subtree
 Traverse to right subtree
And outputs the following: F, B, A, D, C, E, G, I, H
Inorder[edit]
The second(middle) type of traversal is inorder whose code looks like the following:
sub P(TreeNode)
If LeftPointer(TreeNode) != NULL Then
P(TreeNode.LeftNode)
Output(TreeNode.value)
If RightPointer(TreeNode) != NULL Then
P(TreeNode.RightNode)
end sub
This can be summed up as
 Traverse to left subtree
 Visit root node (generally output this)
 Traverse to right subtree
And outputs the following: A, B, C, D, E, F, G, H, I
For sorted binary trees it will output the nodes in order (alphabetical above). Watch out though, sometimes they might give you unordered binary trees to try and trick you!
Postorder[edit]
The last type of traversal is postorder whose code looks like the following:
sub P(TreeNode)
If LeftPointer(TreeNode) != NULL Then
P(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
P(TreeNode.RightNode)
Output(TreeNode.value)
end sub
This can be summed up as
 Traverse to left subtree
 Traverse to right subtree
 Visit root node (generally output this)
And outputs the following: A, C, E, D, B, H, I, G, F
Rule of thumb[edit]
There is an easier way to remember how to do this and if you are struggling for time in the exam you can try this way:
 Check that the code is left traversal followed by right traversal
 Check the position of the output line
 draw the dots on the nodes
 draw a line around the tree
 follow the line and write down each node where you meet a dot
So let's take a look at what that all means. First of all take a look at the code. If the code has the left tree traversal before the right tree traversal we can proceed (this is true in all cases above and below). How we need to find out where the output line is.
sub P(TreeNode)
'Output(TreeNode.value) REM PreOrder
If LeftPointer(TreeNode) != NULL Then
P(TreeNode.LeftNode)
'Output(TreeNode.value) REM InOrder
If RightPointer(TreeNode) != NULL Then
P(TreeNode.RightNode)
'Output(TreeNode.value) REM PostOrder
end sub
Depending on where the line to output the node value is this will tell you what sort of tree order traversal they are asking you to do. NOTE: If you have In order traversal don't jump too soon, the tree may not be sorted!
But how does this help? The next thing you need to do is put a little mark on each node of the tree as follows:
Type of Traversal  Position of Output code  Where to put your mark 

Pre  Top  Left 
In  Middle  Bottom 
Post  Bottom  Right 
Now draw a line around the tree, and follow it around in an anticlockwise fashion. Your end result should look like one of the diagrams below. Check that your rule of thumb answer matches the answers given above.
NOTE: They may try to trick you using one the following ways:
 Right traversal is before left traversal
 The binary tree is not sorted and they want you to perform inorder traversal
If you have time work it out properly and use this method to help.
Breadth First traversal[edit]
 Enqueue the root node.
 Dequeue a node and examine it.
 If the element sought is found in this node, quit the search and return a result.
 Otherwise enqueue any successors (the direct child nodes) that have not yet been discovered.
 If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
 If the queue is not empty, repeat from Step 2.
Note: Using a stack instead of a queue would turn this algorithm into a depthfirst search.
Depth First traversal[edit]
See preorder traversal
Exercise: Depth and Breadth First Traversal
