C Programs | IT Developer
IT Developer

C Programs

Share with a Friend
Previous
HOME
Next

Data Structures in C

Inorder Traversal in Binary Tree

Inorder Traversal in a Binary Tree

Concept Overview

Inorder Traversal is one of the three fundamental Depth-First Traversal methods for binary trees.

Traversal Order:
        Left Subtree → Root → Right Subtree

Key Idea:

  1. Visit the left child recursively.
  2. Visit the root node.
  3. Visit the right child recursively.

For Binary Search Trees (BSTs), Inorder Traversal visits nodes in ascending sorted order.

 

C Program: Inorder Traversal in Binary Tree

C 
#include <stdio.h>


#include <stdlib.h>


 


// Structure definition for a 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));


    if (newNode == NULL) {


        printf("Memory allocation failed!\n");


        exit(1);


    }


    newNode->data = value;


    newNode->left = NULL;


    newNode->right = NULL;


    return newNode;


}


 


// Inorder Traversal Function (Left -> Root -> Right)


void inorderTraversal(struct Node* root) {


    if (root == NULL)


        return;


 


    inorderTraversal(root->left);    // Visit left subtree


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


    inorderTraversal(root->right);   // Visit right subtree


}


 


int main() {


    // Create a simple binary tree manually


    /*


              1


             / \


            2   3


           / \


          4   5


    */


 


    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:\n");


    inorderTraversal(root);


    printf("\n");


 


    return 0;


}

Output

 
OUTPUT :
Inorder Traversal of the Binary Tree:
4 2 5 1 3

Step-by-Step Traversal Explanation

Using the example tree:

       1

      / \

     2   3

    / \

   4   5

Inorder Sequence:

  1. Visit left subtree of 1 → (subtree rooted at 2)
  2. Visit left of 2 → (4) → print 4
  3. Visit root 2 → print 2
  4. Visit right of 2 → (5) → print 5
  5. Back to root 1 → print 1
  6. Visit right of 1 → (3) → print 3

 Output: 4 2 5 1 3

 Key Notes

Concept

Description

Traversal Type

Depth-First Search (DFS)

Order

Left → Root → Right

For BST

Produces elements in ascending sorted order

Implementation

Recursive (can also be done iteratively using a stack)

 

Previous
Next