Tree traversal
A tree is a special case of a graph, and therefore the graph traversal algorithms of the previous chapter also apply to trees. A graph traversal can start at any node, but in the case of a tree the traversal always starts at the root node. Binary trees can be traversed in three additional ways. The following tree will be used as the recurring example.
Breadthfirst
[edit  edit source]Traversing a tree in breadthfirst order means that after visiting a node X, all of X's children are visited, then all of X's 'grandchildren' (i.e. the children's children), then all of X's 'greatgrandchildren', etc. In other words, the tree is traversed by sweeping through the breadth of a level before visiting the next level down, as shown in this animation:
The children of a node may be visited in any order, but remember the algorithm uses a queue, so if a node X is enqueued (grey in the animation) before node Y, then X's children will be visited (black in the animation) before Y's children. For the example tree at the start of this chapter, two possible breadthfirst traversals are F B G A D I C E H and F G B I D A H E C. In the second traversal, G is visited before B, so I is visited before A and D.
Exercise: Breadth First Traversal List two other possible breadthfirst traversals of the same tree. Answer: Since F, B and D each have two children, there are in total 2*2*2=8 possible breadthfirst traversals:
The first and last traversals were already given above, so you could have listed any other two. 
Depthfirst
[edit  edit source]As the name implies, a depthfirst traversal will go down one branch of the tree as far as possible, i.e. until it stops at a leaf, before trying any other branch. The various branches starting from the same parent may be explored in any order. For the example tree, two possible depthfirst traversals are F B A D C E G I H and F G I H B D E C A.
Exercise: Breadth First Traversal List two other possible depthfirst traversals of the same tree. Answer: Since F, B and D each have two children, there are in total 2*2*2=8 possible depthfirst traversals:
The first and last traversals were already given above, so you could have listed any other two. 
Exercise: Depth and Breadth First Traversal

 Depth First traversal generally uses a Stack
 Breadth First generally uses a Queue
Preorder
[edit  edit source]Binary trees are usually traversed from left to right, but righttoleft traversal is also possible and might appear in the exam questions. We will therefore make the direction always clear in the rest of this chapter.
If each node is visited before both of its subtrees, then it's called a preorder traversal. The algorithm for lefttoright preorder traversal is:
 Visit the root node (generally output it)
 Do a preorder traversal of the left subtree
 Do a preorder traversal of the right subtree
which can be implemented as follows, using the tree data structure defined in the previous unit:
sub PreOrder(TreeNode)
Output(TreeNode.value)
If LeftPointer(TreeNode) != NULL Then
PreOrder(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
PreOrder(TreeNode.RightNode)
end sub
Since the algorithm completely determines the order in which nodes are visited, there is only one possible lefttoright preorder traversal for each binary tree. For our example tree, which is a binary tree, it's F B A D C E G I H.
Because a preorder traversal always goes down one branch (left or right) before moving on to the other branch, a preorder traversal is always one of the possible depthfirst traversals.
Postorder
[edit  edit source]If each node is visited after its subtrees, then it's a postorder traversal. The algorithm for lefttoright postorder traversal is:
 Do a postorder traversal of the left subtree
 Do a postorder traversal of the right subtree
 Visit the root node (generally output this)
which can be implemented as:
sub PostOrder(TreeNode)
If LeftPointer(TreeNode) != NULL Then
PostOrder(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
PostOrder(TreeNode.RightNode)
Output(TreeNode.value)
end sub
There is only one lefttoright postorder traversal for each binary tree. For our example tree, it's A C E D B H I G F.
Inorder
[edit  edit source]If each node is visited between visiting its left and right subtrees, then it's an inorder traversal. The algorithm for lefttoright inorder traversal is:
 Do an inorder traversal of the left subtree
 Visit root node (generally output this)
 Do an inorder traversal of the right subtree
which can be implemented as:
sub InOrder(TreeNode)
If LeftPointer(TreeNode) != NULL Then
InOrder(TreeNode.LeftNode)
Output(TreeNode.value)
If RightPointer(TreeNode) != NULL Then
InOrder(TreeNode.RightNode)
end sub
There is only one lefttoright inorder traversal for each binary tree. For our example tree, it's A B C D E F G H I. Note the nodes are visited in ascending order. That's no coincidence.
In binary search trees like our example tree, the values in the left subtree are smaller than the root and the values in the right subtree are larger than the root, so a lefttoright inorder traversal visits the nodes in ascending order.
Exercise: Inorder Traversal Is the statement "an inorder traversal always visits the nodes in ascending order" true or false? Answer: It is false. An inorder traversal only visits the nodes in ascending order if it's a lefttoright traversal and the tree is a binary search tree. How would you change the algorithm above to visit the nodes of a binary search tree in descending order ? Answer: A righttoleft inorder traversal would produce the desired order:

Traversal Tips
[edit  edit source]In the exam, you may be given some traversal pseudocode and a binary tree, and asked to list the nodes in the order the code will visit them.
The first thing is to look carefully at the code and check:
 is the node visited before (preorder), between (inorder) or after (postorder) visiting the subtrees?
 is the left subtree visited before the right subtree or the other way round?
For example, the following code does a lefttoright traversal and the comments show where the visit of the root might take place.
sub Traversal(TreeNode)
'Output(TreeNode.value) REM PreOrder
If LeftPointer(TreeNode) != NULL Then
Traversal(TreeNode.LeftNode)
'Output(TreeNode.value) REM InOrder
If RightPointer(TreeNode) != NULL Then
Traversal(TreeNode.RightNode)
'Output(TreeNode.value) REM PostOrder
end sub
Let's assume it's lefttoright traversal. Once you know, from the position of the node visit, if it's a pre, in or postorder traversal, you can annotate each node of the binary tree as follows:
Type of Traversal  Position of Output code  Where to put your mark 

Pre  Top  Left 
In  Middle  Bottom 
Post  Bottom  Right 
Finally, draw a line going anticlockwise around the tree, connecting the marks. Follow the line and write down each node as you meet a mark: that will be the order in which the code will visit the nodes. Here are the three possible lefttoright traversals:

Preorder
FBADCEGIH 
Inorder
ABCDEFGHI 
Postorder
ACEDBHIGF
As you can see, following this tip you obtain the same answers as in the sections above.
If the traversal is right to left, you have to draw a clockwise line and swap the position of the preorder or postorder mark.
Type of Traversal  Position of Output code  Mark for lefttoright traversal  Mark for righttoleft traversal 

Pre  Top  Left  Right 
In  Middle  Bottom  Bottom 
Post  Bottom  Right  Left 
If the tree is a binary search tree and you're asked for an inorder traversal, you should have visited the nodes in ascending order (for lefttoright traversal) or descending order (for righttoleft traversal). If it's not a binary search tree, the inorder traversal won't visit the nodes in neither ascending nor descending order, but a preorder or postorder traversal might, it will all depend where the nodes are placed in the tree.
Although in this chapter we have always made explicit whether it was a lefttoright or righttoleft traversal for clarity, the typical usage of the terms preorder, inorder and postorder implies a lefttoright traversal, if nothing to the contrary is said.