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