Tree Data Structures in C | Binary Trees, Traversals, Examples

Tree Data Structures in C | Binary Trees, Traversals, Examples

Tree Data Structures in C – Complete Guide with Code Examples

Tree is a fundamental data structure in computer science, commonly used for organizing hierarchical data. In this article, we’ll explore trees in C, particularly focusing on binary trees, various types of tree traversals, and how to implement them in C using pointers and recursion.

🌳 What is a Tree in Data Structure?

A tree is a non-linear, hierarchical data structure composed of nodes. It has one root node and sub-nodes called children. Unlike linear structures like arrays and linked lists, trees allow faster and more structured data search and organization.

Trees are widely used in compilers, operating systems, AI decision trees, file systems, and databases. They form the backbone of many hierarchical models and algorithms such as binary search trees (BST), AVL trees, Heaps, and Trie.

🔧 Structure of a Tree Node in C

Every node in a tree contains data and pointers to its left and right child nodes. Here's the basic structure:

This node structure can be extended to hold more metadata, such as parent pointers or balance factors (in AVL trees). Understanding the use of struct and pointers is essential to master tree implementations in C. 


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

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

🛠️ Creating a New Tree Node

Use dynamic memory allocation to create a new node in C: 


struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}

📥 Inserting Nodes in a Binary Tree (Recursively)

Here’s how you insert nodes to maintain binary search tree properties: 


struct Node* insert(struct Node* root, int value) {
    if (root == NULL) return createNode(value);
    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);
    return root;
}

This recursive method maintains the BST property, which ensures O(log n) time complexity for average-case search, insert, and delete operations. However, in the worst-case (degenerate tree), it can degrade to O(n).

🚶 Tree Traversal in C (In-Order, Pre-Order, Post-Order)

Tree traversal means visiting all nodes in a certain order. C makes this very clean with recursion.

In-Order Traversal (Left → Root → Right)


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

Pre-Order Traversal (Root → Left → Right)


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

Post-Order Traversal (Left → Right → Root)


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

Tree traversals are crucial for applications like expression tree evaluation, serialization of trees, and syntax tree processing in compilers. Recursion simplifies the logic, though iterative versions using stacks also exist.

💥 Full Binary Tree Program in C


int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("In-Order: ");
    inOrder(root);
    printf("\n");

    printf("Pre-Order: ");
    preOrder(root);
    printf("\n");

    printf("Post-Order: ");
    postOrder(root);
    printf("\n");

    return 0;
}

The output of this program will show the nodes in all three traversal orders. Modify the input values to observe different tree shapes and their corresponding traversal results. Try using values that create left-skewed or right-skewed trees.

📚 Variants of Trees in C

There are several advanced types of trees you should explore after mastering binary trees:

  • Binary Search Tree (BST): Maintains sorted order for efficient search.
  • AVL Tree: Self-balancing BST with guaranteed log-time operations.
  • Red-Black Tree: Balanced tree used in STL map/set implementations.
  • Segment Tree: Used for range query problems.
  • Trie (Prefix Tree): Used in autocomplete, dictionary, and spell-check.

🔗 Additional Resources

⚠️ Common Mistakes to Avoid

  • Forgetting to initialize child pointers to NULL
  • Improper handling of dynamic memory leading to memory leaks
  • Incorrect base case in recursive traversal functions
  • Using scanf or printf incorrectly with pointer data types

📌 Final Thoughts

Trees are vital in many computing problems — from parsing expressions to creating efficient search engines and databases. Mastering trees in C equips you with deep system-level understanding and improves your data structure foundation.

Comments

Post a Comment