C Inorder Traversal 🎯

Welcome to this comprehensive guide on C Inorder Traversal! This lesson is designed for beginners and intermediate learners, so let's dive right in.

What is Inorder Traversal? 📝

Inorder traversal is a way to traverse a binary tree by visiting the nodes in the following order: left subtree, root (current node), right subtree. This method is particularly useful for traversing a binary search tree, where the inorder traversal results in a sorted sequence.

Why Inorder Traversal? 💡

Inorder traversal is essential in various real-world applications, such as finding the minimum and maximum values in a tree, sorting a list, and many more.

Binary Trees and Nodes 📝

Before we dive into the traversal, let's quickly review binary trees and nodes. A binary tree is a tree in which each node has at most two children, called the left child and the right child. A node itself is a data structure that contains a piece of data and a reference to its children.

Implementing Inorder Traversal 🎯

Now that we've covered the basics, let's write a simple C program for inorder traversal of a binary tree.

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

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

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

    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    struct Node* root = NULL;
    root = (struct Node*) malloc(sizeof(struct Node));
    root->data = 50;
    root->left = NULL;
    root->right = NULL;

    root->left = (struct Node*) malloc(sizeof(struct Node));
    root->left->data = 30;
    root->left->left = NULL;
    root->left->right = NULL;

    root->right = (struct Node*) malloc(sizeof(struct Node));
    root->right->data = 70;
    root->right->left = NULL;
    root->right->right = NULL;

    inorder(root);
    return 0;
}

In this example, we create a simple binary tree with the root node at 50, left node at 30, and right node at 70. The inorder function takes a node as an argument and performs the traversal by calling itself recursively on the left and right subtrees.

Advanced Inorder Traversal 🎯

For more complex trees, you might encounter situations where you need to perform operations on each node during traversal. Here's an example of modifying our previous program to perform an operation on each node:

void inorder(struct Node* root, int* sum) {
    if (root == NULL)
        return;

    inorder(root->left, sum);
    *sum += root->data;
    inorder(root->right, sum);
}

int main() {
    struct Node* root = NULL;
    int sum = 0;

    // Same tree as before...

    inorder(root, &sum);
    printf("The sum of the tree is: %d\n", sum);
    return 0;
}

In this example, we pass a pointer to an integer sum to the inorder function. Inside the function, we increment sum by the data of each node as we traverse the tree.

Quiz 🎯

With this, you've learned the basics of C Inorder Traversal. Keep practicing and exploring to deepen your understanding! 💡