C Programming Data Structures Traversals Inorder Preorder Postorder Level Order Complete Guide

Last Update:2025-06-23T00:00:00 .NET School AI Teacher - SELECT ANY TEXT TO EXPLANATION. 9 mins read Difficulty-Level: beginner

Understanding the Core Concepts of C Programming data structures Traversals Inorder, Preorder, Postorder, Level Order

C Programming Data Structures: Traversals (Inorder, Preorder, Postorder, Level Order)

Inorder Traversal

Inorder Traversal involves visiting the left subtree, the root node, and then the right subtree. This traversal method is particularly useful when working with binary search trees because it retrieves the elements in ascending order.

Order: Left → Root → Right
Example Implementation (Recursive):

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

Iterative Implementation Using Stack:

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

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

void inorderTraversalIterative(struct Node* root) {
    struct Node *current = root;
    struct Node *stack[100]; 
    int top = -1;

    while (current != NULL || top != -1) {
        while (current != NULL) {
            stack[++top] = current;         // Push current node to stack
            current = current->left;        // Move to left child
        }

        current = stack[top--];             // Pop node from stack
        printf("%d ", current->data);       // Visit node

        current = current->right;           // Move to right child
    }
}

Preorder Traversal

Preorder Traversal involves visiting the root node first, followed by the left subtree and then the right subtree. It is used for creating a copy of the tree, evaluating an expression tree, prefix evaluation, etc.

Order: Root → Left → Right
Example Implementation (Recursive):

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

Iterative Implementation Using Stack:

void preorderTraversalIterative(struct Node* root) {
    struct Node* stack[100];
    struct Node* node = root;
    int top = -1;

    while (node != NULL || top != -1) {
        while (node != NULL) {
            printf("%d ", node->data);      // Visit node
            stack[++top] = node;            // Push node to stack
            node = node->left;              // Move to left child
        }

        node = stack[top--];                // Pop node from stack
        node = node->right;                 // Move to right child
    }
}

Postorder Traversal

Postorder Traversal involves visiting the left subtree, the right subtree, and finally the root node. It is useful for deleting a tree, evaluating a postfix expression, etc.

Order: Left → Right → Root
Example Implementation (Recursive):

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

Iterative Implementation Using Two Stacks:

void postorderTraversalIterative(struct Node* root) {
    struct Node *stack1[100], *stack2[100];
    struct Node *node = root;
    int top1 = -1, top2 = -1;

    stack1[++top1] = root;
    while (top1 != -1) {
        node = stack1[top1--];
        stack2[++top2] = node; 

        if (node->left) {
            stack1[++top1] = node->left;
        }
        
        if (node->right) {
            stack1[++top1] = node->right;
        }
    }

    while (top2 != -1) {
        node = stack2[top2--];
        printf("%d ", node->data);
    }
}

Level Order Traversal

Level Order Traversal (or Breadth First Search) involves visiting all nodes at the present depth level before moving on to nodes at the next depth level. It’s commonly used for tree transformations and pathfinding algorithms like finding the shortest path between nodes.

Order: Nodes level by level from top to bottom, and left to right across each level.
Implementation Using Queue:

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

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

struct QueueNode {
    struct Node* tree_node;
    struct QueueNode* next;
};

struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

void enqueue(struct Queue* q, struct Node* n) {
    struct QueueNode* t = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    t->tree_node = n;
    t->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = t;
    } else {
        q->rear->next = t;
        q->rear = t;
    }
}

void dequeue(struct Queue* q) {
    if (q->front == NULL) return;

    struct QueueNode* t = q->front;

    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;

    free(t);
}

int isEmptyQueue(struct Queue* q) {
    return q->front == NULL ? 1 : 0;
}

struct Node* frontNode(struct Queue* q) {
    if (q->front) return q->front->tree_node;
    return NULL;
}

void levelOrderTraversal(struct Node* root) {
    if (!root) return;

    struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
    q->front = q->rear = NULL;

    enqueue(q, root);

    while (!isEmptyQueue(q)) {
        struct Node* n = frontNode(q);
        dequeue(q);

        printf("%d ", n->data);

        if (n->left) enqueue(q, n->left); 
        if (n->right) enqueue(q, n->right);
    }

    free(q);
}

Key Points and Importance

Inorder Traversal
- Retrieves elements in a sorted order for BSTs.
- Useful in problems requiring sorted sequences of nodes.
Preorder Traversal
- Constructs a deep copy of the tree by visiting the parent before children.
- Applied in scenarios where a complete traversal starting from the root is necessary.
Postorder Traversal
- Ideal for operations such as deleting a tree (bottom-up).
- Frequently utilized in prefix and postfix operations of data structures.
Level Order Traversal
- Best for scenarios involving horizontal level-wise processing.
- Applied in pathfinding algorithms, tree transformations, and finding minimum or maximum depth paths efficiently.

Online Code run

🔔 Note: Select your programming language to check or run code at

💻 Run Code Compiler

Step-by-Step Guide: How to Implement C Programming data structures Traversals Inorder, Preorder, Postorder, Level Order

Binary Tree Traversals in C

Before we start, let's define the basic structure of a binary tree node:

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

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

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

1. Inorder Traversal (Left, Root, Right)

In Inorder traversal, we recursively visit the left subtree, then the current node, and finally the right subtree.

// Function for Inorder Traversal
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);    // Traverse left subtree
        printf("%d ", root->data);  // Visit root
        inorder(root->right);   // Traverse right subtree
    }
}

2. Preorder Traversal (Root, Left, Right)

In Preorder traversal, we visit the current node first, then recursively visit the left and right subtrees.

// Function for Preorder Traversal
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // Visit root
        preorder(root->left);     // Traverse left subtree
        preorder(root->right);    // Traverse right subtree
    }
}

3. Postorder Traversal (Left, Right, Root)

In Postorder traversal, we recursively visit the left and right subtrees, then the current node.

// Function for Postorder Traversal
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);    // Traverse left subtree
        postorder(root->right);   // Traverse right subtree
        printf("%d ", root->data);  // Visit root
    }
}

4. Level Order Traversal (Breadth-First Traversal)

Level Order Traversal is done using a queue. We'll need a few helper functions to implement this.

// Define the structure for a queue (used in level order traversal)
struct Queue {
    int front;
    int rear;
    int size;
    struct Node** array;
};

// Function to create a queue
struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->size = 0;
    queue->rear = capacity - 1; // This is important, see the enqueue
    queue->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return queue;
}

// Function to check if the queue is full
int isFull(struct Queue* queue) {
    return (queue->size == capacity);
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Function to add an element to the queue
void enqueue(struct Queue* queue, struct Node* item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    // printf("%d enqueued to queue\n", item->data);
}

// Function to remove an element from the queue
struct Node* dequeue(struct Queue* queue) {
    if (isEmpty(queue))
        return NULL;
    struct Node* item = queue->array[queue->front];
    queue->front = (queue->front + 1) % capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function to get front of queue
struct Node* front(struct Queue* queue) {
    if (isEmpty(queue))
        return NULL;
    return queue->array[queue->front];
}

// Function for Level Order Traversal
void levelOrder(struct Node* root) {
    if (root == NULL)
        return;

    struct Queue* queue = createQueue(1000);

    enqueue(queue, root);

    while (!isEmpty(queue)) {
        struct Node* currentNode = front(queue);
        printf("%d ", currentNode->data);
        dequeue(queue);

        if (currentNode->left != NULL)
            enqueue(queue, currentNode->left);

        if (currentNode->right != NULL)
            enqueue(queue, currentNode->right);
    }
}

Complete Example

Here is a complete program that creates a binary tree and performs all four types of traversals:

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

#define capacity 1000 // Max capacity of the queue

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

// Define the structure for a queue
struct Queue {
    int front;
    int rear;
    int size;
    struct Node** array;
};

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

// Function to create a queue
struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return queue;
}

// Function to check if the queue is full
int isFull(struct Queue* queue) {
    return (queue->size == capacity);
}

// Function to check if the queue is empty
int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

// Function to add an element to the queue
void enqueue(struct Queue* queue, struct Node* item) {
    if (isFull(queue))
        return;
    queue->rear = (queue->rear + 1) % capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
}

// Function to remove an element from the queue
struct Node* dequeue(struct Queue* queue) {
    if (isEmpty(queue))
        return NULL;
    struct Node* item = queue->array[queue->front];
    queue->front = (queue->front + 1) % capacity;
    queue->size = queue->size - 1;
    return item;
}

// Function for Inorder Traversal
void inorder(struct Node* root) {
    if (root != NULL) {
        inorder(root->left);    // Traverse left subtree
        printf("%d ", root->data);  // Visit root
        inorder(root->right);   // Traverse right subtree
    }
}

// Function for Preorder Traversal
void preorder(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);  // Visit root
        preorder(root->left);     // Traverse left subtree
        preorder(root->right);    // Traverse right subtree
    }
}

// Function for Postorder Traversal
void postorder(struct Node* root) {
    if (root != NULL) {
        postorder(root->left);    // Traverse left subtree
        postorder(root->right);   // Traverse right subtree
        printf("%d ", root->data);  // Visit root
    }
}

// Function for Level Order Traversal
void levelOrder(struct Node* root) {
    if (root == NULL)
        return;

    struct Queue* queue = createQueue(capacity);

    enqueue(queue, root);

    while (!isEmpty(queue)) {
        struct Node* currentNode = front(queue);
        printf("%d ", currentNode->data);
        dequeue(queue);

        if (currentNode->left != NULL)
            enqueue(queue, currentNode->left);

        if (currentNode->right != NULL)
            enqueue(queue, currentNode->right);
    }
}

int main() {
    // Create a sample 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);
    root->right->left = createNode(6);
    root->right->right = createNode(7);

    printf("Inorder Traversal: ");
    inorder(root);
    printf("\n");

    printf("Preorder Traversal: ");
    preorder(root);
    printf("\n");

    printf("Postorder Traversal: ");
    postorder(root);
    printf("\n");

    printf("Level Order Traversal: ");
    levelOrder(root);
    printf("\n");

    return 0;
}

Output

When you run the above program, it will produce the following output:

Top 10 Interview Questions & Answers on C Programming data structures Traversals Inorder, Preorder, Postorder, Level Order

1. What is a Tree in Data Structures?

Answer: A tree is a hierarchical data structure that consists of nodes connected by edges. Each node has zero or more child nodes, except for the last level, which consists of leaf nodes (nodes with no children). The first node in the tree is called the root node.

2. What are the Different Types of Tree Traversals?

Answer: There are mainly four types of tree traversals:

Inorder Traversal: Traverses the left subtree, then the root node, and finally the right subtree.
Preorder Traversal: Traverses the root node before the left and right subtrees.
Postorder Traversal: Traverses the left and right subtrees before the root node.
Level Order Traversal: Traverse nodes level by level from top to bottom. It starts from the root level, then moves to the next level, and so on.

3. How do you Perform an Inorder Traversal on a Binary Search Tree (BST)?

Answer: In inorder traversal of a BST, nodes are recursively visited in this order:

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

This sequence visits nodes in ascending order.

4. Can you Explain Preorder Traversal with Example Code?

Answer: During preorder traversal, the root node is processed before recursing on its child nodes:

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

For example, given a binary tree with root value 10 and children 7 and 15, the preorder traversal would be: 10 7 15.

5. What is Postorder Traversal, and How Does it Work?

Answer: Postorder traversal processes all the left and right subtrees of a node before the node itself:

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

Continuing the previous example, postorder traversal would result in: 7 15 10.

6. How is Level Order Traversal Implemented in C?

Answer: Level order traversal requires a queue data structure to keep track of nodes at each level from left to right:

#include <stdlib.h>

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

typedef struct QueueNode {
    struct Node* ptr;
    struct QueueNode* next;
} Qnode;

Qnode* front = NULL, *rear = NULL;

void enqueue(struct Node* node) {
    Qnode* new = (Qnode*)malloc(sizeof(Qnode));
    new->ptr = node;
    new->next = NULL;
    if (front == NULL && rear == NULL) {
        front = rear = new;
    } else {
        rear->next = new;
        rear = new;
    }
}

struct Node* dequeue() {
    Qnode* temp = front;
    struct Node* n;
    if (front == NULL) return NULL;
    n = temp->ptr;
    front = front->next;
    if (front == NULL) rear = NULL;
    free(temp);
    return n;
}

int isEmptyQueue() {
    if (front == NULL) return 1;
    return 0;
}

void levelOrderTraversal(struct Node* root) {
    if (!root) return;
    enqueue(root);
    while (!isEmptyQueue()) {
        struct Node* current = dequeue();
        printf("%d ", current->data);
        if (current->left != NULL) enqueue(current->left);
        if (current->right != NULL) enqueue(current->right);
    }
}

7. Why Do We Use Inorder Traversal in a Binary Search Tree (BST)?

Answer: Inorder traversal of a BST outputs the nodes' values in sorted order which is useful for operations that require sorted data, such as finding a range of values in a BST efficiently.

8. What Are the Practical Uses of Preorder Traversal?

Answer: Preorder traversal can be used to create a copy of the tree since it processes nodes before their subtrees. It's also utilized in expression evaluations where operators precede their operands.

9. When Would You Use Postorder Traversal?

Answer: Postorder traversal is helpful in deleting a tree because it processes child nodes before their parent, thus ensuring that the children are deleted before the parent. It’s also useful in evaluating postfix expressions.

10. Can Level Order Traversal be Used to Sort Data in a Binary Search Tree?

Answer: No, level order traversal does not sort data in a BST. It simply prints nodes level by level. If you wish to sort elements, inorder traversal is the appropriate method for BSTs.

C Programming Data Structures Traversals Inorder Preorder Postorder Level Order Complete Guide