Binary Tree traversal in C: In-Order, Pre-Order, Post-Order

Last update on December 20 2024 13:17:41 (UTC/GMT +8 hours)

Write a C program to find the traversal order (pre-order, in-order, post-order) of a binary tree that represents a graph.

From Wikipdeia,

In computer science, graph traversal (also known as graph search) refers to the process of visiting (checking and/or updating) each vertex in a graph. Such traversals are classified by the order in which the vertices are visited. Tree traversal is a special case of graph traversal.

Sample Solution:

C Code:

#include <stdio.h>
#include <limits.h>
#include 
#include 

// Structure for a binary tree node
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

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

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

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

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

int main() {
    // Constructing a sample binary tree
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    // Output the traversal orders
    printf("In-order Traversal: ");
    inOrderTraversal(root);
    printf("\n");

    printf("Pre-order Traversal: ");
    preOrderTraversal(root);
    printf("\n");

    printf("Post-order Traversal: ");
    postOrderTraversal(root);
    printf("\n");

    return 0;
}

Output:

Binary Tree:
        1
       / \
      2   3
     / \
    4   5
--------------------------------------------------
Traversal Orders:

In-order Traversal: 4 2 5 1 3
Pre-order Traversal: 1 2 4 5 3
Post-order Traversal: 4 5 2 3 1

Explanation:

In the exercise above,

The struct Node represents a binary tree node with integer data, left child (left), and right child (right).
The newNode function creates a new node with the given key.
The "inOrderTraversal()", "preOrderTraversal()", and "postOrderTraversal()" functions perform in-order, pre-order, and post-order traversals, respectively, printing the node data at each step.
In the "main()" function, a sample binary tree is constructed, and the three types of traversals are applied, printing the results.

Flowchart:

C Programming Code Editor:

Previous: Dijkstra's Algorithm for shortest paths in C.