Tree traversal algorithms for a binary tree

For the tree above, a tree traversal can be performed in 3 different ways.

Pre-order

The first type of traversal is pre-order 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:

1. Visit the root node (generally output this)
2. Traverse to left subtree
3. Traverse to right subtree

The code outputs the following: F, B, A, D, C, E, G, I, H

In-order

The second (middle) type of traversal is in-order 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:

1. Traverse to left subtree
2. Visit root node (generally output this)
3. Traverse to right subtree

The code outputs the following: A, B, C, D, E, F, G, H, I

For sorted binary trees it will output the nodes in order (in alphabetical order in this case). Watch out though, sometimes you might encounter unordered binary trees that will not produce a sorted list when read in-order!

Post-order

The last type of traversal is post-order 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:

1. Traverse to left subtree
2. Traverse to right subtree
3. Visit root node (generally output this)

The code outputs the following: A, C, E, D, B, H, I, G, F

Rule of thumb

There is an easier way to remember how to do this and if you don't have enough time in the exam you can try this way:

1. Check that the code is left traversal followed by right traversal
2. Check the position of the output line
3. Draw the dots on the nodes
4. Draw a line around the tree
5. 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, 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 Pre-Order
   If LeftPointer(TreeNode) != NULL Then
      P(TreeNode.LeftNode)
   'Output(TreeNode.value) REM In-Order
   If RightPointer(TreeNode) != NULL Then
      P(TreeNode.RightNode)
   'Output(TreeNode.value)  REM Post-Order
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 anti-clockwise fashion. Your end result should look like one of the diagrams below. Check that your rule of thumb answer matches the answers given above.

• The 3 different types of traversal
• 
  Pre-order Traversal
  FBADCEGIH
• 
  In-order Traversal
  ABCDEFGHI
• 
  Post-order Traversal
  ACEDBHIGF

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 in-order traversal

If you have time work it out properly and use this method to help.

Exercise: Binary Tree Traversal For the following binary tree perform the following: Pre-order traversal In-order traversal Post-order traversal Answer: Pre-order traversal: GEBDFKMR In-order traversal: BDEFGKMR Post-order traversal: DBFERMKG What does the following code describe: sub P(TreeNode) If LeftPointer(TreeNode) != NULL Then P(TreeNode.LeftNode) Output(TreeNode.value) If RightPointer(TreeNode) != NULL Then P(TreeNode.RightNode) end sub Answer: In-Order traversal because the output is in the centre and the left node is traversed before the right node. For the following binary tree what does the following code do? sub P(TreeNode) If LeftPointer(TreeNode) != NULL Then P(TreeNode.LeftNode) If RightPointer(TreeNode) != NULL Then P(TreeNode.RightNode) Output(TreeNode.value) end sub Answer: post-Order traversal because the output is at the bottom and the left node is traversed before the right node. Using the following binary tree: what would be the outputs for: Pre-order traversal In-order traversal Post-order traversal Answer: Pre-order traversal: 7,5,4,2,3,8,9,1 In-order traversal: 4,2,5,3,7,9,8,1 Post-order traversal: 2,4,3,5,9,1,8,7

Breadth First traversal

1. Enqueue the root node.
2. 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.
3. If the queue is empty, every node on the graph has been examined – quit the search and return "not found".
4. If the queue is not empty, repeat from Step 2.

Animated example of a breadth-first search

Note: Using a stack instead of a queue would turn this algorithm into a depth-first search.

Depth First traversal

See pre-order traversal. Depth first traversal and pre-order traversal are equivalent.

Exercise: Depth and Breadth First Traversal Perform breadth and depth-first traversal on the following: Answer: Depth First: F, B, A, D, C, E, G, I, H Breadth First: F, B, G, A, D, I, C, E, H Answer: Depth First: G, E, B, D, F, K, M, R Breadth First: G, E, K, B, F, M, D, R