Data Structures and Algorithms in C (DSA)

📘 Chapter: Binary Tree Traversals (Pre, In, Post)

After understanding the basic structure and representation of Binary Trees, the next crucial step is learning how to systematically visit (or "traverse") every node in the tree. Unlike linear data structures, where traversal is straightforward (e.g., iterating through an array from start to end), trees offer multiple paths. Binary tree traversals are algorithms that visit each node in a specific order, which is essential for various operations like printing tree contents, copying trees, or converting trees to other data structures.

🚶‍♂️ What are Tree Traversals?

Tree traversal refers to the process of visiting each node in a tree exactly once in a predefined order. For binary trees, the most common traversal methods are classified as Depth-First Traversals. These methods explore as far as possible along each branch before backtracking. The three primary depth-first traversals are:

• Preorder Traversal: Visit the root, then the left subtree, then the right subtree.
• Inorder Traversal: Visit the left subtree, then the root, then the right subtree.
• Postorder Traversal: Visit the left subtree, then the right subtree, then the root.

These traversals are typically implemented recursively, leveraging the hierarchical nature of trees.

📋 The Three Depth-First Traversals

1. Preorder Traversal (Root-Left-Right)

In Preorder traversal, we process the current node first, then recursively traverse its left subtree, and finally its right subtree.

• Visit the **Root** node.
• Recursively traverse the **Left** subtree.
• Recursively traverse the **Right** subtree.

// Conceptual C code for Preorder Traversal
void preorderTraversal(struct Node* node) {
    if (node == NULL)
        return;
    printf("%d ", node->data);        // 1. Visit Root
    preorderTraversal(node->left);   // 2. Traverse Left
    preorderTraversal(node->right);  // 3. Traverse Right
}
  

Use Cases:

• Creating a copy of the tree.
• For prefix expressions (e.g., `+ A B`).
• Representing a file system structure (directory listing).

2. Inorder Traversal (Left-Root-Right)

In Inorder traversal, we first recursively traverse the left subtree, then process the current node, and finally recursively traverse its right subtree.

• Recursively traverse the **Left** subtree.
• Visit the **Root** node.
• Recursively traverse the **Right** subtree.

// Conceptual C code for Inorder Traversal
void inorderTraversal(struct Node* node) {
    if (node == NULL)
        return;
    inorderTraversal(node->left);   // 1. Traverse Left
    printf("%d ", node->data);        // 2. Visit Root
    inorderTraversal(node->right);  // 3. Traverse Right
}
  

Use Cases:

• For Binary Search Trees (BSTs), Inorder traversal yields elements in non-decreasing (sorted) order.
• For infix expressions (e.g., `A + B`).

3. Postorder Traversal (Left-Right-Root)

In Postorder traversal, we first recursively traverse the left subtree, then the right subtree, and finally process the current node.

• Recursively traverse the **Left** subtree.
• Recursively traverse the **Right** subtree.
• Visit the **Root** node.

// Conceptual C code for Postorder Traversal
void postorderTraversal(struct Node* node) {
    if (node == NULL)
        return;
    postorderTraversal(node->left);   // 1. Traverse Left
    postorderTraversal(node->right);  // 2. Traverse Right
    printf("%d ", node->data);        // 3. Visit Root
}
  

Use Cases:

• Deleting a tree (delete children before parent).
• For postfix expressions (e.g., `A B +`).

Binary Tree Traversal Example Visualization

🌐 Breadth-First Traversal (Level Order Traversal)

While Depth-First Traversals go deep into one branch before moving to another, Breadth-First Traversal (also known as Level Order Traversal) visits all nodes at the current level before moving to the next level. This is typically implemented using a queue.

// Conceptual C code for Level Order Traversal
#include 
#include 
// (Assume Node structure as defined in previous chapter)
// (Assume Queue implementation is available)

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

    // Create a queue and enqueue root
    struct Queue* q = createQueue(); // Assume this function exists
    enqueue(q, root);

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

        // Enqueue left child
        if (current->left != NULL)
            enqueue(q, current->left);

        // Enqueue right child
        if (current->right != NULL)
            enqueue(q, current->right);
    }
    destroyQueue(q); // Clean up
}
  

Use Cases:

• Finding the shortest path in an unweighted graph (trees are a type of graph).
• Level-by-level processing, such as printing nodes at each level.

📌 Real-Life Example (UdaanPath)

Tree traversals have practical applications on platforms like UdaanPath for organizing and presenting hierarchical data:

• Course Module Navigation (Preorder/Level Order): A course structure often resembles a tree (Course -> Modules -> Lessons -> Sub-lessons).
  • Preorder traversal could be used to generate a linear table of contents, where a module is listed before its lessons.
  • Level Order traversal could be used to display an overview of all modules at the top level, then all lessons, etc., presenting a structured view level by level on a dashboard.
• Quiz/Assessment Flow (Preorder): If a quiz has branching questions (e.g., "If you answer A, go to Q3; if B, go to Q4"), the possible question paths can form a tree. Preorder traversal might define the default linear progression through questions.
• Knowledge Graph/Ontology Display (Preorder/Inorder): If UdaanPath builds a knowledge graph of interconnected topics (e.g., "Data Structures" -> "Arrays", "Linked Lists", "Trees"), traversals could be used to generate structured reports or visual representations. Inorder traversal on a BST-like structure of topics could list them alphabetically.
• Code Structure/Syntax Highlighting (Postorder): Internally, compilers or code editors might use parse trees for code. Postorder traversal is often used to evaluate expressions (operands first, then operator) or to free memory by deleting child nodes before parent nodes.

✅ Summary: Systematically Visiting Nodes

• Tree Traversals are algorithms to visit every node in a tree in a specific order.
• The three main Depth-First Traversals are:
  • Preorder (Root-Left-Right): Used for copying trees, prefix expressions.
  • Inorder (Left-Root-Right): Used for sorted output in BSTs, infix expressions.
  • Postorder (Left-Right-Root): Used for deleting trees, postfix expressions.
• Breadth-First Traversal (Level Order): Visits nodes level by level, typically using a queue, useful for shortest path or level-wise processing.
• Traversals are essential for processing hierarchical data in various applications.

📤 Coming Next: Binary Search Tree (BST)

With a solid understanding of basic binary tree structure and how to traverse them, we're now ready to explore a highly practical and widely used specialized binary tree: the Binary Search Tree (BST). This data structure combines the advantages of linked lists and sorted arrays for efficient search, insertion, and deletion operations.