C Program for Inorder Traversal of Binary Tree

In C, inorder traversal of a binary tree can be done using a recursive function like void inorder(struct Node* root) { if (root != NULL) { inorder(root->left); printf("%d ", root->data); inorder(root->right); } } which visits left child, root, then right child.

Examples

InputBinary tree with root 1, left child 2, right child 3

Output2 1 3

InputBinary tree with root 4, left subtree (2,1,3), right subtree (6,5,7)

Output1 2 3 4 5 6 7

InputEmpty tree (root is NULL)

Output

How to Think About It

To do inorder traversal, think of visiting the left side of the tree first, then the current node, and finally the right side. You do this by calling the same process on the left child, then printing the current node's value, then calling the process on the right child. This naturally fits a recursive approach.

Algorithm

1

Check if the current node is NULL; if yes, return.

2

Recursively call inorder traversal on the left child.

3

Print the current node's data.

4

Recursively call inorder traversal on the right child.

Code

c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

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;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    inorder(root);
    return 0;
}

Output

2 1 3 

Dry Run

Let's trace the inorder traversal on a tree with root 1, left child 2, and right child 3.

1

Start at root

Current node is 1, call inorder on left child (2).

2

Visit left child

Current node is 2, call inorder on left child (NULL), returns immediately.

3

Print node 2

Print 2, then call inorder on right child (NULL), returns immediately.

4

Back to root

Print 1, then call inorder on right child (3).

5

Visit right child

Current node is 3, call inorder on left child (NULL), returns immediately.

6

Print node 3

Print 3, then call inorder on right child (NULL), returns immediately.

Step	Current Node	Action	Output So Far
1	1	Go left
2	2	Go left (NULL)
3	2	Print 2	2
4	2	Go right (NULL)	2
5	1	Print 1	2 1
6	1	Go right	2 1
7	3	Go left (NULL)	2 1
8	3	Print 3	2 1 3
9	3	Go right (NULL)	2 1 3

Why This Works

Step 1: Recursive calls follow left subtree first

The function calls itself on the left child first to reach the leftmost node before printing.

Step 2: Print current node after left subtree

After finishing left subtree, the current node's data is printed, ensuring left nodes come before root.

Step 3: Then visit right subtree

Finally, the function calls itself on the right child to print nodes on the right side.

Alternative Approaches

Iterative inorder traversal using stack

c

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

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

struct Stack {
    struct Node* data[100];
    int top;
};

void push(struct Stack* s, struct Node* node) {
    s->data[++(s->top)] = node;
}

struct Node* pop(struct Stack* s) {
    return s->data[(s->top)--];
}

int isEmpty(struct Stack* s) {
    return s->top == -1;
}

void inorder(struct Node* root) {
    struct Stack s;
    s.top = -1;
    struct Node* current = root;

    while (current != NULL || !isEmpty(&s)) {
        while (current != NULL) {
            push(&s, current);
            current = current->left;
        }
        current = pop(&s);
        printf("%d ", current->data);
        current = current->right;
    }
}

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;
}

int main() {
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);

    inorder(root);
    return 0;
}

This method avoids recursion and uses a stack to track nodes, useful when recursion depth is a concern.

Complexity: O(n) time, O(h) space

Time Complexity

The traversal visits each node exactly once, so the time is proportional to the number of nodes, O(n).

Space Complexity

The space depends on the recursion stack or explicit stack size, which is proportional to the tree height h, O(h).

Which Approach is Fastest?

Both recursive and iterative methods have the same time complexity; iterative avoids recursion overhead but uses extra stack memory.

Approach	Time	Space	Best For
Recursive inorder	O(n)	O(h)	Simple code, small to medium trees
Iterative inorder	O(n)	O(h)	Very deep trees or when recursion is limited