Binary Tree Traversal Algorithms

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