This program demonstrates how to perform in-order, pre-order, and post-order traversals on a binary tree in C, displaying nodes in each traversal order.

Program Explanation

The program is structured into several functions:

• Node Structure: Defines the structure of a binary tree node.
• Function to Create a New Node: Allocates a new node with given data.
• In-order Traversal Function: Recursively visits nodes in left-root-right order.
• Pre-order Traversal Function: Recursively visits nodes in root-left-right order.
• Post-order Traversal Function: Recursively visits nodes in left-right-root order.
• Main Function: Demonstrates the tree traversals by creating a binary tree and performing each traversal.

Program Code

// Include necessary headers
#include <stdio.h>
#include <stdlib.h>

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

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

// Function to perform in-order traversal
void inOrder(Node* root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->data);
        inOrder(root->right);
    }
}

// Function to perform pre-order traversal
void preOrder(Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// Function to perform post-order traversal
void postOrder(Node* root) {
    if (root != NULL) {
        postOrder(root->left);
        postOrder(root->right);
        printf("%d ", root->data);
    }
}

// Main function to demonstrate the tree traversals
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("In-order traversal: ");
    inOrder(root);
    printf("\\n");

    printf("Pre-order traversal: ");
    preOrder(root);
    printf("\\n");

    printf("Post-order traversal: ");
    postOrder(root);
    printf("\\n");

    return 0;
}
    

Key Components of the Program:

• Node Structure: Defines each node of the binary tree.
• newNode Function: Helps to allocate and initialize a new node with specified data.
• Traversal Functions: Each function performs a different type of traversal:
  • inOrder: Processes the left child, then the node itself, then the right child.
  • preOrder: Processes the node first, then the left child, then the right child.
  • postOrder: Processes the left child, then the right child, and finally the node itself.
• Main Function: Constructs a sample binary tree, performs each of the three traversals, and prints the results to demonstrate the different traversal orders.

This program clearly separates the creation and traversal of the binary tree, showcasing how each traversal strategy works and the typical use cases for each.