A tree is a particular case of a graph, and due to this fact the graph traversal algorithms of the earlier chapter additionally apply to timber.
A graph traversal can begin at any node, however within the case of a tree the traversal at all times begins on the root node. Binary timber will be traversed in three extra methods. The next tree might be used because the recurring instance.
Breadthfirst[edit]
Traversing a tree in breadthfirst order signifies that after visiting a node X, all of X’s youngsters are visited, then all of X’s ‘grandchildren’ (i.e. the youngsters’s youngsters), then all of X’s ‘greatgrandchildren’, and so on. In different phrases, the tree is traversed by sweeping by way of the breadth of a stage earlier than visiting the subsequent stage down, as proven on this animation:
The youngsters of a node could also be visited in any order, however keep in mind the algorithm makes use of a queue, so if a node X is enqueued (gray within the animation) earlier than node Y, then X’s youngsters might be visited (black within the animation) earlier than Y’s youngsters. For the instance tree in the beginning of this chapter, two potential breadthfirst traversals are F B G A D I C E H and F G B I D A H E C. Within the second traversal, G is visited earlier than B, so I is visited earlier than A and D.
Train: Breadth First Traversal Listing two different potential breadthfirst traversals of the identical tree. Reply: Since F, B and D every have two youngsters, there are in complete 2*2*2=8 potential breadthfirst traversals:
The primary and final traversals had been already given above, so you can have listed some other two. 
Depthfirst[edit]
Because the title implies, a depthfirst traversal will go down one department of the tree so far as potential, i.e. till it stops at a leaf, earlier than attempting some other department. The assorted branches ranging from the identical guardian could also be explored in any order. For the instance tree, two potential depthfirst traversals are F B A D C E G I H and F G I H B D E C A.
Train: Breadth First Traversal Listing two different potential depthfirst traversals of the identical tree. Reply: Since F, B and D every have two youngsters, there are in complete 2*2*2=8 potential depthfirst traversals:
The primary and final traversals had been already given above, so you can have listed some other two. 
Train: Depth and Breadth First Traversal Listing one breadthfirst and one depthfirst traversal for this tree: Reply: The potential depthfirst traversals are
The potential breadthfirst traversals are

 Depth First traversal typically makes use of a Stack
 Breadth First typically makes use of a Queue
Preorder[edit]
Binary timber are normally traversed from left to proper, however righttoleft traversal can also be potential and would possibly seem within the examination questions. We’ll due to this fact make the route at all times clear in the remainder of this chapter.
If every node is visited earlier than each of its subtrees, then it is referred to as a preorder traversal.
The algorithm for lefttoright preorder traversal is:
 Go to the basis node (typically output it)
 Do a preorder traversal of the left subtree
 Do a preorder traversal of the appropriate subtree
which will be carried out as follows, utilizing the tree knowledge construction outlined within the earlier unit:
sub PreOrder(TreeNode)
Output(TreeNode.worth)
If LeftPointer(TreeNode) != NULL Then
PreOrder(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
PreOrder(TreeNode.RightNode)
finish sub
Because the algorithm utterly determines the order by which nodes are visited, there is just one potential lefttoright preorder traversal for every binary tree. For our instance tree, which is a binary tree, it is F B A D C E G I H.
As a result of a preorder traversal at all times goes down one department (left or proper) earlier than shifting on to the opposite department, a preorder traversal is at all times one of many potential depthfirst traversals.
Put uporder[edit]
If every node is visited after its subtrees, then it is a submitorder traversal. The algorithm for lefttoright postorder traversal is:
 Do a postorder traversal of the left subtree
 Do a postorder traversal of the appropriate subtree
 Go to the basis node (typically output this)
which will be carried out as:
sub PostOrder(TreeNode)
If LeftPointer(TreeNode) != NULL Then
PostOrder(TreeNode.LeftNode)
If RightPointer(TreeNode) != NULL Then
PostOrder(TreeNode.RightNode)
Output(TreeNode.worth)
finish sub
There is just one lefttoright postorder traversal for every binary tree. For our instance tree, it is A C E D B H I G F.
Inorder[edit]
If every node is visited between visiting its left and proper subtrees, then it is an inorder traversal. The algorithm for lefttoright inorder traversal is:
 Do an inorder traversal of the left subtree
 Go to root node (typically output this)
 Do an inorder traversal of the appropriate subtree
which will be carried out as:
sub InOrder(TreeNode)
If LeftPointer(TreeNode) != NULL Then
InOrder(TreeNode.LeftNode)
Output(TreeNode.worth)
If RightPointer(TreeNode) != NULL Then
InOrder(TreeNode.RightNode)
finish sub
There is just one lefttoright inorder traversal for every binary tree. For our instance tree, it is A B C D E F G H I. Word the nodes are visited in ascending order. That is no coincidence.
In binary search timber like our instance tree, the values within the left subtree are smaller than the basis and the values in the appropriate subtree are bigger than the basis, so a lefttoright inorder traversal visits the nodes in ascending order.
Train: Inorder Traversal Is the assertion “an inorder traversal at all times visits the nodes in ascending order” true or false? Reply: It’s false. An inorder traversal solely visits the nodes in ascending order if it is a lefttoright traversal and the tree is a binary search tree. How would you alter the algorithm above to go to the nodes of a binary search tree in descending order ? Reply: A righttoleft inorder traversal would produce the specified order:

Traversal Ideas[edit]
Within the examination, you might be given some traversal pseudocode and a binary tree, and requested to listing the nodes within the order the code will go to them.
The very first thing is to look fastidiously on the code and examine:
 is the node visited earlier than (preorder), between (inorder) or after (postorder) visiting the subtrees?
 is the left subtree visited earlier than the appropriate subtree or the opposite method spherical?
For instance, the next code does a lefttoright traversal and the feedback present the place the go to of the basis would possibly happen.
sub Traversal(TreeNode)
'Output(TreeNode.worth) REM PreOrder
If LeftPointer(TreeNode) != NULL Then
Traversal(TreeNode.LeftNode)
'Output(TreeNode.worth) REM InOrder
If RightPointer(TreeNode) != NULL Then
Traversal(TreeNode.RightNode)
'Output(TreeNode.worth) REM Put upOrder
finish sub
Let’s assume it is lefttoright traversal. As soon as , from the place of the node go to, if it is a pre, in or postorder traversal, you possibly can annotate every node of the binary tree as follows:
Kind of Traversal  Place of Output code  The place to place your mark 

Pre  High  Left 
In  Center  Backside 
Put up  Backside  Proper 
Lastly, draw a line going anticlockwise across the tree, connecting the marks. Observe the road and write down every node as you meet a mark: that would be the order by which the code will go to the nodes. Listed below are the three potential lefttoright traversals:
As you possibly can see, following this tip you get hold of the identical solutions as within the sections above.
If the traversal is correct to left, it’s important to draw a clockwise line and swap the place of the preorder or postorder mark.
Kind of Traversal  Place of Output code  Mark for lefttoright traversal  Mark for righttoleft traversal 

Pre  High  Left  Proper 
In  Center  Backside  Backside 
Put up  Backside  Proper  Left 
If the tree is a binary search tree and also you’re requested for an inorder traversal, you need to have visited the nodes in ascending order (for lefttoright traversal) or descending order (for righttoleft traversal). If it isn’t a binary search tree, the inorder traversal will not go to the nodes in neither ascending nor descending order, however a preorder or postorder traversal would possibly, it is going to all rely the place the nodes are positioned within the tree.
Though on this chapter now we have at all times made specific whether or not it was a lefttoright or righttoleft traversal for readability, the everyday utilization of the phrases preorder, inorder and postorder implies a lefttoright traversal, if nothing on the contrary is claimed.
Train: Binary Tree Traversal For the next binary tree carry out a preorder, an inorder and a postorder traversal. Reply: When nothing else is claimed, a lefttoright traversal is assumed.
What traversal does the next code describe: sub Traverse(TreeNode)
If LeftPointer(TreeNode) != NULL Then
Traverse(TreeNode.LeftNode)
Output(TreeNode.worth)
If RightPointer(TreeNode) != NULL Then
Traverse(TreeNode.RightNode)
finish sub
Reply: An inorder traversal, as a result of the node go to is within the centre of the code and the left subtree is traversed earlier than the appropriate subtree. What does the next code do? sub P(TreeNode)
If RightPointer(TreeNode) != NULL Then
P(TreeNode.RightNode)
If LeftPointer(TreeNode) != NULL Then
P(TreeNode.LeftNode)
Output(TreeNode.worth)
finish sub
Reply: It does a righttoleft postorder traversal, as a result of it first visits the appropriate subtree, then the left subtree and eventually the node. Utilizing the next binary tree:
Reply:
