C Program to Traverse a Binary Tree Using Inorder Traversal

C Program to Traverse a Binary Tree Using Inorder Traversal

By /

Inorder traversal is a method of visiting all nodes in a binary tree by visiting the left subtree first, then the root node, and finally the right subtree. This traversal method is especially important for binary search trees because it prints the nodes in ascending order. Understanding inorder traversal is crucial for operations like sorting, searching, and evaluating expressions in tree-based structures.

Understanding the Problem

Traversing a binary tree requires visiting every node exactly once while following a specific order. In inorder traversal, the left child is processed before the current node, and the right child is processed afterward. Implementing this recursively ensures simplicity and correctness, but iterative approaches using stacks are also possible for larger trees or memory-constrained environments.

Program: Recursive Inorder Traversal of a Binary Tree

This program demonstrates how to traverse a binary tree in inorder fashion, printing each node’s value using recursion. Nodes are created dynamically and linked to form the tree.

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

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

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Recursive inorder traversal
void inorderRecursive(Node *root) {

    if (root != NULL) {
        inorderRecursive(root->left);
        printf("%d ", root->data);
        inorderRecursive(root->right);
    }

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);

    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Recursive Inorder Traversal: ");
    inorderRecursive(root);
    printf("\n");

    return 0;

}

In this program, the Node structure contains data, left, and right pointers. The createNode function dynamically allocates memory for each node. The inorderRecursive function visits the left subtree, prints the current node’s value, and then traverses the right subtree. Using recursion ensures that every node is visited exactly once in the correct inorder sequence.

Program: Iterative Inorder Traversal of a Binary Tree

This program demonstrates how to traverse a binary tree in inorder fashion without recursion, using an explicit stack to keep track of nodes.

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

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

// Stack structure
typedef struct Stack {
    Node **arr;
    int top;
    int capacity;
} Stack;

// Function to create a new node
Node* createNode(int value) {

    Node *newNode = (Node*) malloc(sizeof(Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;

    return newNode;

}

// Stack functions
Stack* createStack(int capacity) {

    Stack *stack = (Stack*) malloc(sizeof(Stack));
    stack->arr = (Node**) malloc(capacity * sizeof(Node*));
    stack->top = -1;
    stack->capacity = capacity;

    return stack;

}

void push(Stack *stack, Node *node) {

    if (stack->top < stack->capacity - 1) {
        stack->arr[++stack->top] = node;
    }

}

Node* pop(Stack *stack) {

    if (stack->top >= 0) {
        return stack->arr[stack->top--];
    }

    return NULL;

}

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

// Iterative inorder traversal
void inorderIterative(Node *root) {

    Stack *stack = createStack(100);
    Node *current = root;

    while (current != NULL || !isEmpty(stack)) {

        while (current != NULL) {
            push(stack, current);
            current = current->left;
        }

        current = pop(stack);
        printf("%d ", current->data);
        current = current->right;

    }

}

int main() {

    Node *root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(20);
    root->left->left = createNode(3);
    root->left->right = createNode(7);
    root->right->left = createNode(15);

    printf("Iterative Inorder Traversal: ");
    inorderIterative(root);
    printf("\n");

    return 0;

}

In this program, the Stack structure stores nodes temporarily, simulating the call stack that recursion would normally use. The algorithm pushes left children until the end, pops nodes to visit them, and moves to the right subtree. This ensures every node is visited exactly once in inorder sequence without recursion.

The recursive inorder traversal is simple and easy to read, making it ideal for small to medium trees or when clarity is more important than efficiency. The iterative inorder traversal uses an explicit stack, which avoids potential stack overflow and is better suited for very deep or large trees where memory control and stability are critical. Essentially, recursion is handy for simplicity, while iteration is handy for robustness in large structures.

FAQs

Q1: What is the difference between inorder, preorder, and postorder traversals?
Inorder visits left, root, right; preorder visits root, left, right; postorder visits left, right, root.

Q2: Is inorder traversal used only for binary search trees?
No, it can be used for any binary tree, but it outputs sorted values only for BSTs.

Q3: Can we implement inorder traversal iteratively?
Yes, a stack can be used to implement inorder traversal without recursion.

Q4: What is the time complexity of inorder traversal?
O(n), where n is the number of nodes, because each node is visited once.

Conclusion

Inorder traversal is a fundamental technique for accessing all nodes in a binary tree in a specific order. It is particularly useful for binary search trees where it returns values in ascending order. Mastering this traversal builds a foundation for understanding more advanced tree algorithms and applications.

References & Additional Resources

A curated collection of books and online resources providing both theoretical foundations and practical examples for understanding binary trees, dynamic memory allocation, and related data structures in C.

  1. Thareja, R. (2011). Data Structures Using C. Oxford University Press – Detailed coverage of binary trees, dynamic memory allocation, and other fundamental data structures.
  2. Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – Classic reference on C fundamentals, including pointers and memory, essential for data structure implementation.
  3. GeeksforGeeks: Binary Tree in C – Explanation of binary tree concepts, structure, and implementation in C.
  4. GeeksforGeeks: Binary Tree Traversal in C – Covers inorder, preorder, and postorder traversal techniques with examples.
  5. Programiz: Data Structures – Binary Tree – Beginner-friendly guide with examples for traversal, insertion, and deletion.
  6. Tutorialspoint: What is Dynamic Memory Allocation in C? – Explanation of malloc(), calloc(), realloc(), and free() functions for memory management.

Related Posts

Scroll to Top