C Program to Traverse a Binary Tree Using Inorder Traversal

Introduction

Inorder traversal is one of the depth-first traversal methods for binary trees. In an inorder traversal, the nodes are recursively visited in the following order: left subtree, root node, right subtree. This traversal method is particularly useful when you want to retrieve the elements of a binary search tree in sorted order.

Example:

• Tree Structure:

       1
      / \
     2   3
    / \
   4   5
  

• Inorder Traversal Output: 4 2 5 1 3

Problem Statement

Create a C program that:

• Constructs a binary tree.
• Traverses the binary tree using inorder traversal.
• Outputs the nodes in the order they are visited.

Solution Steps

1. Include the Standard Libraries: Use #include <stdio.h> and #include <stdlib.h> for standard input-output and memory allocation functions.
2. Define the Structure for a Tree Node: Each node will contain a data value and pointers to its left and right children.
3. Implement the Inorder Traversal Function: This function will traverse the binary tree in inorder.
4. Create a Main Function: Build a sample binary tree and perform inorder traversal.

C Program to Traverse a Binary Tree Using Inorder Traversal

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

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

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

// Function to perform inorder traversal of the binary tree
void inorderTraversal(struct Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);    // Traverse the left subtree
        printf("%d ", root->data);       // Visit the root node
        inorderTraversal(root->right);   // Traverse the right subtree
    }
}

int main() {
    // Creating 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);

    // Perform inorder traversal
    printf("Inorder traversal of the binary tree is: ");
    inorderTraversal(root);
    printf("\n");

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Structure for a Tree Node

• The struct Node defines a node of the binary tree, which contains an integer data and pointers to its left and right children.

Function to Create a New Tree Node

• The newNode function creates a new node with the given data, initializes its left and right pointers to NULL, and returns the pointer to the new node.

Function to Perform Inorder Traversal

• The inorderTraversal function recursively visits nodes in the order: left subtree, root node, right subtree. The function uses a simple base case: if the current node is not NULL, it proceeds with the traversal; otherwise, it returns.

Main Function

• The main function constructs a sample binary tree and calls the inorderTraversal function to print the nodes in inorder.

Output Example

Example Output:

Inorder traversal of the binary tree is: 4 2 5 1 3

Example Output (Different Tree):

If the binary tree is modified, for example:

       10
      /  \
     20   30
    / \
   40  50

The inorder traversal will be:

Inorder traversal of the binary tree is: 40 20 50 10 30

Conclusion

This C program demonstrates how to traverse a binary tree using inorder traversal. Inorder traversal is a fundamental technique in binary tree processing, particularly in binary search trees, where it retrieves the nodes in sorted order. The program provides a practical example of how to implement and use inorder traversal in C programming.