C Program to Perform Inorder, Preorder, and Postorder Traversal of a Binary Tree

1. Introduction

Tree traversal is a cornerstone concept in computer science and is crucial when working with tree data structures. There are three common ways to traverse a binary tree:

1. Inorder (Left, Root, Right)

2. Preorder (Root, Left, Right)

3. Postorder (Left, Right, Root)

In this blog post, we'll implement and understand these three traversal methods using a binary tree.

2. Program Overview

Our program will perform the following tasks:

1. Define a structure for a binary tree node.

2. Implement functions to insert nodes into the tree.

3. Implement functions for inorder, preorder, and postorder traversal.

4. Demonstrate tree traversal using a sample binary tree.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Define the structure for a binary tree node
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to insert a node into a binary tree
Node* insert(Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else if (value > root->data) {
        root->right = insert(root->right, value);
    }
    return root;
}

// Function for inorder traversal
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

// Function for preorder traversal
void preorder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preorder(root->left);
        preorder(root->right);
    }
}

// Function for postorder traversal
void postorder(Node* root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        printf("%d ", root->data);
    }
}

int main() {
    Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root = insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);

    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    printf("Preorder traversal: ");
    preorder(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorder(root);
    printf("\n");

    return 0;
}

Output:

Inorder traversal: 20 30 40 50 60 70 80
Preorder traversal: 50 30 20 40 70 60 80
Postorder traversal: 20 40 30 60 80 70 50

4. Step By Step Explanation

1. We start by defining the structure for a binary tree node. Each node contains an integer (data), a pointer to the left child, and a pointer to the right child.

2. The createNode function is used to dynamically allocate memory for a new node and initialize it with a given value.

3. Using the insert function, we can add nodes to our binary tree.

4. The inorder, preorder, and postorder functions are recursive and used to perform the respective tree traversal.

5. In the main function, we demonstrate the tree traversals using a sample binary tree.

Now, when you execute this program, it will display the binary tree elements in three different orders as specified by the traversal methods.