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