Understanding Tree Traversal Algorithms in C

Trees are fundamental non-linear data structures in computer science, used to represent hierarchical relationships. From file systems and organizational charts to abstract syntax trees in compilers, their applications are vast. To process the data stored within a tree, we often need to visit each node exactly once. This systematic process is known as tree traversal.

In this guide, part of our C Language Series, we'll dive deep into the most common methods for traversing binary trees: Pre-order, In-order, and Post-order traversal, along with an introduction to Level-order traversal. We'll explore their logic, implementation in C, and practical use cases.

The Anatomy of a Tree Node

Before we can traverse a tree, let's define its basic building block: the node. For a binary tree, each node typically contains data and pointers to its left and right children. If a child doesn't exist, its pointer will be NULL.

#include <stdio.h>
#include <stdlib.h> // For malloc and exit

// Define the structure for a 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));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        exit(EXIT_FAILURE); // Exit if memory allocation fails
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Recursive Traversal Techniques for Binary Trees

The three primary traversal methods—Pre-order, In-order, and Post-order—are inherently recursive for binary trees. They differ only in the order in which they visit (process) the root node relative to its left and right subtrees.

1. Pre-order Traversal (Root, Left, Right)

In Pre-order traversal, we visit the root node first, then recursively traverse its left subtree, and finally recursively traverse its right subtree.

• Visit Root: Process the current node's data.
• Traverse Left: Recursively call pre-order on the left child.
• Traverse Right: Recursively call pre-order on the right child.

Use Cases:

• Creating a copy of the tree.
• Representing decision trees or parsing expressions (useful for prefix notation, e.g., + AB).

void preOrderTraversal(struct Node* root) {
    if (root != NULL) {
        printf("%d ", root->data);   // 1. Visit Root
        preOrderTraversal(root->left);  // 2. Traverse Left
        preOrderTraversal(root->right); // 3. Traverse Right
    }
}

2. In-order Traversal (Left, Root, Right)

In In-order traversal, we first recursively traverse the left subtree, then visit the root node, and finally recursively traverse its right subtree.

• Traverse Left: Recursively call in-order on the left child.
• Visit Root: Process the current node's data.
• Traverse Right: Recursively call in-order on the right child.

Use Cases:

• Retrieving elements of a Binary Search Tree (BST) in sorted order. This is its most significant application.
• Used in expression trees to get infix notation (e.g., A + B).

void inOrderTraversal(struct Node* root) {
    if (root != NULL) {
        inOrderTraversal(root->left);  // 1. Traverse Left
        printf("%d ", root->data);     // 2. Visit Root
        inOrderTraversal(root->right); // 3. Traverse Right
    }
}

3. Post-order Traversal (Left, Right, Root)

In Post-order traversal, we first recursively traverse the left subtree, then recursively traverse its right subtree, and finally visit the root node.

• Traverse Left: Recursively call post-order on the left child.
• Traverse Right: Recursively call post-order on the right child.
• Visit Root: Process the current node's data.

Use Cases:

• Deleting a tree: Children must be deleted before their parent to prevent memory leaks.
• Evaluating postfix expressions (e.g., AB+).

void postOrderTraversal(struct Node* root) {
    if (root != NULL) {
        postOrderTraversal(root->left);  // 1. Traverse Left
        postOrderTraversal(root->right); // 2. Traverse Right
        printf("%d ", root->data);       // 3. Visit Root
    }
}

Building Our Example Tree

Let's construct a simple binary tree to demonstrate these traversals. We'll build a tree that looks like this (values represent node data):

        1
       / \
      2   3
     / \
    4   5

// Function to build the example tree
struct Node* buildExampleTree() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    return root;
}

Putting It All Together: A Complete Example

Here's a main function that ties together our node creation, tree building, and traversal functions, demonstrating the output of each method.

// --- Main function for demonstration ---
int main() {
    struct Node* root = buildExampleTree();

    printf("Pre-order Traversal: ");
    preOrderTraversal(root); // Expected: 1 2 4 5 3
    printf("\n");

    printf("In-order Traversal: ");
    inOrderTraversal(root);  // Expected: 4 2 5 1 3
    printf("\n");

    printf("Post-order Traversal: ");
    postOrderTraversal(root); // Expected: 4 5 2 3 1
    printf("\n");

    // Important: In real-world applications, you would need to free the
    // dynamically allocated memory for all nodes to prevent memory leaks.
    // A post-order traversal is typically used for this purpose:
    // void freeTree(struct Node* node) {
    //     if (node == NULL) return;
    //     freeTree(node->left);
    //     freeTree(node->right);
    //     free(node);
    // }
    // freeTree(root);

    return 0;
}

Expected Output for the Example Tree:

Pre-order Traversal: 1 2 4 5 3 
In-order Traversal: 4 2 5 1 3 
Post-order Traversal: 4 5 2 3 1 

Level-Order Traversal (Breadth-First Search)

Unlike the recursive traversals which are Depth-First Searches (DFS), Level-order traversal processes nodes level by level, starting from the root. It's also known as Breadth-First Search (BFS).

Implementing level-order traversal typically requires a queue data structure to store nodes at the current level, and then processing their children in the next level. Let's provide a simplified example with a basic array-based queue for demonstration purposes.

// --- Basic Queue Implementation for Level-Order Traversal ---
// For a full-fledged application, a more robust dynamic queue (e.g., linked list)
// would be recommended. This is a simple fixed-size array implementation.
#define MAX_QUEUE_SIZE 100

// Global queue and pointers (simplified for example)
struct Node* queue[MAX_QUEUE_SIZE];
int front = -1;
int rear = -1;

void enqueue(struct Node* node) {
    if (rear == MAX_QUEUE_SIZE - 1) {
        printf("Queue is full, cannot enqueue %d!\n", node->data);
        return;
    }
    if (front == -1) { // First element being enqueued
        front = 0;
    }
    rear++;
    queue[rear] = node;
}

struct Node* dequeue() {
    if (front == -1 || front > rear) { // Queue is empty
        // printf("Queue is empty, cannot dequeue!\n");
        return NULL;
    }
    struct Node* node = queue[front];
    front++;
    // If front crosses rear, queue is conceptually empty, reset pointers
    if (front > rear) { 
        front = -1;
        rear = -1;
    }
    return node;
}

// Level-Order Traversal function
void levelOrderTraversal(struct Node* root) {
    if (root == NULL) {
        return;
    }

    // Reset queue state for each traversal call
    front = -1; 
    rear = -1;

    enqueue(root);

    while (front != -1) { // While queue is not empty
        struct Node* current = dequeue();
        if (current == NULL) break; // Should not happen if queue logic is correct

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

        if (current->left != NULL) {
            enqueue(current->left);
        }
        if (current->right != NULL) {
            enqueue(current->right);
        }
    }
}

To integrate this with our main function, you would add the queue definition and traversal call:

int main() {
    struct Node* root = buildExampleTree();

    // ... (previous Pre-order, In-order, Post-order calls) ...

    printf("Level-order Traversal: ");
    levelOrderTraversal(root); // Expected: 1 2 3 4 5
    printf("\n");

    // Remember to free the tree memory when done
    // freeTree(root); 

    return 0;
}

Expected Output for Level-order Traversal:

Level-order Traversal: 1 2 3 4 5

Why Tree Traversal Matters

Understanding tree traversal is crucial for various programming tasks:

• Data Searching: Efficiently locating specific data within a tree (especially in Binary Search Trees).
• Tree Manipulation: Inserting, deleting, or updating nodes.
• Expression Evaluation: Parsing and evaluating mathematical or logical expressions.
• Serialization/Deserialization: Storing a tree structure to a file and rebuilding it from there.
• Algorithmic Foundations: Many advanced tree algorithms and graph algorithms (like BFS/DFS) build upon these basic traversal patterns.

Conclusion

Tree traversal is a cornerstone concept in data structures. Whether you need to process data in a specific order, flatten a tree, or manage its memory, the Pre-order, In-order, Post-order, and Level-order methods provide the fundamental patterns. By mastering these recursive and iterative techniques, you gain powerful tools for working with hierarchical data in C and beyond.

Keep practicing, and happy coding!