Inorder Traversal of Binary Tree

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

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

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

// Function for inorder traversal
void inorderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }

    // Recursively traverse the left subtree
    inorderTraversal(root->left);

    // Visit the root node
    printf("%d ", root->data);

    // Recursively traverse the right subtree
    inorderTraversal(root->right);
}

int main() {
    // Creating nodes of the binary tree
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

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

    return 0;
}

Explanation of the Code:

1. Structure Definition:
   • We define a structure Node to represent a node of the binary tree.
   • Each node contains three elements:
     • data: Holds the value of the node.
     • left: Pointer to the left child.
     • right: Pointer to the right child.
2. createNode() Function:
   • This function allocates memory for a new node, sets the data field, and initializes the left and right pointers to NULL.
   • It returns a pointer to the newly created node.
3. inorderTraversal() Function:
   • This function takes the root node of a binary tree as input.
   • It uses recursion to traverse the tree in the following order:
     • First, it calls inorderTraversal() for the left subtree.
     • Then, it prints the data of the current node.
     • Finally, it calls inorderTraversal() for the right subtree.
   • If the root is NULL (base condition), it simply returns, ending that branch of recursion.
4. main() Function:
   • This function serves as the entry point of the program.
   • We create a sample binary tree with 5 nodes.
   • The tree looks like this:

     1
    / \
   2   3
  / \
 4   5

Output:

When the program is run, the output will be:

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

Explanation of the Output:

For the given binary tree:

1. Start at the root (1):
   • Traverse the left subtree of 1 (which is 2).
2. At node 2:
   • Traverse the left subtree of 2 (which is 4).
   • 4 is a leaf node (no children), so we print 4.
3. Back to node 2:
   • After visiting 4, we print 2.
   • Then, we traverse the right subtree of 2 (which is 5).
4. At node 5:
   • 5 is a leaf node, so we print 5.
5. Back to the root (1):
   • After finishing the left subtree, we print 1.
   • Then, traverse the right subtree of 1 (which is 3).
6. At node 3:
   • 3 is a leaf node, so we print 3.

Thus, the output of the inorder traversal is 4 2 5 1 3.