Binary Tree Traversal Methods in Data Structure

There are three standard ways of traversing a binary tree T with root R.
1. Preorder Traversal
2. Inorder Traversal
3. Postorder Traversal

Preorder Traversal:

1. Process the root R.
2. Traverse the left sub-tree of R in preorder.
3. Traverse the right sub-tree of R in preorder.

Algorithm for Recursive Preorder Traversal:

Algorithm fnRecursivePreorder(ptrRoot)
{
  if(ptrRoot!=NULL)
  {
   print(ptrRoot->info);
   fnRecursivePreorder(ptrRoot->ptrLeft);
   fnRecursivePreorder(ptrRoot->ptrRight);
  }
}  // End of Algorithm

Inorder Traversal:

1. Traverse the left sub-tree of the root R in inorder.
2. Process the root R.
3. Traverse the right sub-tree of the root R in inorder.

Algorithm for Non-Recursive Inorder Traversal:

Algorithm fnNonRecursiveInorder(ptrRoot)
{
  TreeNode *P;
  P=ptrRoot;
  Initialize stack St;
 while(!empty(St) || P!=NULL)
 {
   while(P!=NULL)
   {
    fnPush(St, P);
    P=P->ptrLeft;
   }
   if(!empty(St))
   {
     P=fnPop(St);
     print P->ptrRight;
   }
 }
}  // End of Algorithm

Postorder Traversal:

1. Traverse the left sub-tree of R in postorder.
2. Traverse the right sub-tree of R in postorder.
3. Process the root R.

Algorithm for Recursive Postorder Traversal:

Algorithm fnRecursivePostorder(ptrRoot)
{
  if(ptrRoot!=NULL)
  {
    fnRecursivePostorder(ptrRoot->ptrLeft);
    fnRecursivePostorder(ptrRoot->ptrRight);
    print(ptrRoot->info);
  }
}  // End of Algorithm