This tutorial discusses different ways for traversing a binary tree (pre-order, post-order, in-order) with algorithms.
Binary Tree Traversal
A binary tree can be traversed in three different ways, namely, pre-order, post-order and in-order. The order in which the nodes are visited differs between these techniques.
In-order Traversal of Binary Tree
The following operations are done recursively at each node to traverse a non-empty binary tree in order.
- Traverse the left subtree of R in inorder.
- Process the root, R.
- Traverse the right subtree of R in inorder.

The algorithm for in-order traversal is given below:
Algorithm: INORDER
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: INORDER(TREE -> LEFT)
Step 3: Write TREE -> DATA
Step 4: INORDER(TREE -> RIGHT)
[END OF LOOP]
Step 5: END
Pre-order Traversal of Binary Tree
The following operations are done recursively at each node to traverse a non-empty binary tree in pre-order. Pre-order traversal is also called depth-first traversal.
- Process the root, R.
- Traverse the left subtree of R in preorder.
- Traverse the right subtree of R in preorder.

The algorithm for pre-order traversal is given below:
Algorithm: PREORDER
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: Write TREE -> DATA
Step 3: PREORDER(TREE -> LEFT)
Step 4: PREORDER(TREE -> RIGHT)
[END OF LOOP]
Step 5: END
Post-order Traversal of Binary Tree
The following operations are done recursively at each node to traverse a non-empty binary tree in post-order.
- Traverse the left subtree of R in postorder.
- Traverse the right subtree of R in postorder.
- Process the root, R.

The algorithm for post-order traversal is given below:
Algorithm: POSTORDER
Step 1: Repeat Steps 2 to 4 while TREE != NULL
Step 2: POSTORDER(TREE -> LEFT)
Step 3: POSTORDER(TREE -> RIGHT)
Step 4: Write TREE -> DATA
[END OF LOOP]
Step 5: END
Example
Consider the following tree. The sequence of nodes that will be visited using different traversal algorithms is also given.

Implementation In C
We create the following tree and implement different traversal algorithms using C.

#include <stdio.h>
#include <stdlib.h>
struct node
{
int item;
struct node *left;
struct node *right;
};
// In-order traversal algorithm
void inOrder(struct node *root)
{
if (root == NULL)
return;
inOrder(root->left);
printf(" %d ", root->item);
inOrder(root->right);
}
// pre-order Traversal algorithm
void preOrder(struct node *root)
{
if (root == NULL)
return;
printf(" %d ", root->item);
preOrder(root->left);
preOrder(root->right);
}
// post-order traversal algorithm
void postOrder(struct node *root)
{
if (root == NULL)
return;
postOrder(root->left);
postOrder(root->right);
printf(" %d ", root->item);
}
// create a new Node
struct node *createNode(item)
{
struct node *newNode = malloc(sizeof(struct node));
newNode->item = item;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
// insert a node at the left
struct node *inserAtLeft(struct node *root, int item)
{
root->left = createNode(item);
return root->left;
}
// insert a node at the right
struct node *insertAtRight(struct node *root, int item)
{
root->right = createNode(item);
return root->right;
}
int main()
{
struct node *root = createNode(2);
inserAtLeft(root, 5);
insertAtRight(root, 6);
inserAtLeft(root->left, 9);
insertAtRight(root->left, 4);
printf("Inorder traversal : ");
inOrder(root);
printf("\nPreorder traversal : ");
preOrder(root);
printf("\nPostorder traversal : ");
postOrder(root);
}
Output
Inorder traversal : 9 5 4 2 6 Preorder traversal : 2 5 9 4 6 Postorder traversal : 9 4 5 6 2

tysm!