# 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*/
}
}
```