Traversing a Binary Tree in C

There are generally 3 traversal strategies for Binary Trees – INORDER, PREORDER and POSTORDER. For eg:, the inorder, preorder and postorder traversal of an expression tree gives the infix, prefix and postfix forms of the expression. Such a traversal could be used to evaluate the value of expression.

Example 1 : Consider the following Binary Tree –

                         A
                       /
                      B
                    /   \
                   C     D
                 /  \   /  \
                E    F  G   H
                 \     \   /  \
                  I     J  K   L

INORDER traversal:

1. traverse left subtree
2. visit root
3. traverse right subtree
Inorder form –> EICFJBGDKHLA

POSTORDER traversal:

1. traverse left subtree
2. traverse right subtree
3. visit root
Postorder form –> IEJFCKLHGDBA

PREORDER traversal:

1. visit root
2. traverse left subtree
3. traverse right subtree
Preorder form –> ABCEIFJDGHKL

Example 2:

                   +
                 /   \
                A     *
                    /   \
                   -     $
                 /  \   /  \
                B    C D    *
                           /  \
                           E   F

Using the steps from Example 1, we can derive the below traversals -

INORDER   (Left, Root, Right) : A + (B - C) * D $ (E * F)

PREORDER  (Root, Left, Right) : +A*-BC$D*EF  

POSTORDER (Left, Right, Root) : ABC-DEF*$*+

Recursive C routine for inorder traversal

void intrav(NODEPTR){
      if(tree != NULL){
           intrav(tree->left);/*traverse left subtree*/
           printf("%d",tree->info);/*visit root*/
           intrav(tree->right);/*traverse rightsubtree*/
      }
}

Recursive C routine for preorder traversal

void pretrav(NODEPTR){
      if(tree != NULL){
           printf("%d",tree->info);/*visit root*/
           intrav(tree->left);/*traverse left subtree*/           
           intrav(tree->right);/*traverse rightsubtree*/
      }
}

Recursive C routine for postorder traversal

void posttrav(NODEPTR){
      if(tree != NULL){           
           intrav(tree->left);/*traverse left subtree*/           
           intrav(tree->right);/*traverse rightsubtree*/
           printf("%d",tree->info);/*visit root*/
      }
}