Trees

Lesson 35

Trees in C are hierarchical data structures that organize data in a parent-child relationship using nodes and edges. A binary tree allows each node at most two children, and a Binary Search Tree (BST) enables efficient searching, insertion, and deletion. Trees are widely used in file systems, databases, compilers, and search algorithms.

C Track

Save progress as you learn.

44 lessons

Lesson content

Trees in C Programming: A Complete Beginner to Advanced Guide

What are Trees in C Programming?

Trees in C programming are hierarchical data structures that organize data in a parent-child relationship. Unlike arrays and linked lists, which store data linearly, trees arrange data in multiple levels, making them ideal for representing hierarchical information.

Think of a family tree. At the top is the oldest ancestor, followed by children, grandchildren, and so on. Similarly, a tree starts with a root node, and every node can have one or more child nodes.

Why Do Trees Exist?

Linear data structures work well for sequential data, but many real-world problems involve hierarchical relationships. Trees solve problems such as fast searching, efficient data organization, representing hierarchical relationships, reducing search time, and organizing sorted data.

Real-World Use Cases

Trees are widely used in:

File systems
Database indexing
Search engines
Expression evaluation
XML and HTML parsing
Artificial Intelligence
Compiler design
Decision trees
Routing algorithms

Prerequisites

Before learning Trees in C, you should understand:

Variables
Data types
Functions
Structures
Pointers
Dynamic memory allocation
Linked Lists (recommended)

Core Concepts

What is a Tree?

A tree is a non-linear data structure consisting of nodes connected by edges. The top node is called the root, and the bottom nodes are called leaf nodes.

Tree Terminology

Term	Meaning
Root	The first node in the tree
Parent	A node with one or more children
Child	A node connected below a parent
Leaf	A node with no children
Edge	Connection between two nodes
Height	Longest path from root to a leaf
Depth	Distance from the root to a node
Subtree	A tree inside another tree

Binary Tree

A binary tree is a tree in which every node has at most two children. Each node contains data, a left child pointer, and a right child pointer.

Binary Tree Node Structure

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

Tree Traversals

Tree traversal means visiting every node exactly once. There are four common traversal methods:

Traversal	Order
Preorder	Root → Left → Right
Inorder	Left → Root → Right
Postorder	Left → Right → Root
Level Order	Level by level

Binary Search Tree (BST)

A Binary Search Tree (BST) is a special type of binary tree where every left child is smaller than its parent and every right child is larger than its parent. BSTs allow efficient searching, insertion, and deletion.

Code Examples

Example 1: Beginner – Create a Tree Node

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node                             // Define tree node
{
    int data;                           // Store node value
    struct Node *left;                  // Pointer to left child
    struct Node *right;                 // Pointer to right child
};

int main()
{
    struct Node *root = (struct Node *)malloc(sizeof(struct Node)); // Allocate memory

    if(root == NULL)                    // Check allocation success
    {
        printf("Memory allocation failed.\n"); // Display error
        return 1;                       // Exit program
    }

    root->data = 10;                    // Store value
    root->left = NULL;                  // No left child
    root->right = NULL;                 // No right child

    printf("%d\n", root->data);         // Print root value

    free(root);                         // Free memory

    return 0;                           // End program
}

Output: 10

Example 2: Beginner – Create a Simple Binary Tree

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Node value
    struct Node *left;                  // Left child
    struct Node *right;                 // Right child
};

int main()
{
    struct Node *root = (struct Node *)malloc(sizeof(struct Node));      // Root node
    struct Node *leftNode = (struct Node *)malloc(sizeof(struct Node));  // Left child
    struct Node *rightNode = (struct Node *)malloc(sizeof(struct Node)); // Right child

    if(root == NULL || leftNode == NULL || rightNode == NULL)
    {
        printf("Memory allocation failed.\n");
        free(root);
        free(leftNode);
        free(rightNode);
        return 1;
    }

    root->data = 1;                     // Root value
    leftNode->data = 2;                 // Left child value
    rightNode->data = 3;                // Right child value

    root->left = leftNode;              // Connect left child
    root->right = rightNode;            // Connect right child

    leftNode->left = NULL;              // No children
    leftNode->right = NULL;

    rightNode->left = NULL;
    rightNode->right = NULL;

    printf("%d %d %d\n", root->data, root->left->data, root->right->data);

    free(leftNode);
    free(rightNode);
    free(root);

    return 0;
}

Output: 1 2 3

Example 3: Intermediate – Inorder Traversal

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Node value
    struct Node *left;                  // Left child
    struct Node *right;                 // Right child
};

void inorder(struct Node *root)         // Inorder traversal
{
    if(root == NULL)                    // Base case
    {
        return;                         // Stop recursion
    }

    inorder(root->left);                // Visit left subtree

    printf("%d ", root->data);          // Visit root

    inorder(root->right);               // Visit right subtree
}

int main()
{
    struct Node root = {2, NULL, NULL}; // Root node
    struct Node left = {1, NULL, NULL}; // Left child
    struct Node right = {3, NULL, NULL}; // Right child

    root.left = &left;                  // Connect left child
    root.right = &right;                // Connect right child

    inorder(&root);                     // Traverse tree

    return 0;
}

Output: 1 2 3

Example 4: Intermediate – Search in a Binary Search Tree

#include <stdio.h>                      // Include standard input/output library

struct Node
{
    int data;                           // Node value
    struct Node *left;                  // Left child
    struct Node *right;                 // Right child
};

int search(struct Node *root, int key)  // Search function
{
    if(root == NULL)                    // Tree is empty
    {
        return 0;                       // Not found
    }

    if(root->data == key)               // Value found
    {
        return 1;                       // Success
    }

    if(key < root->data)                // Search left subtree
    {
        return search(root->left, key);
    }

    return search(root->right, key);    // Search right subtree
}

int main()
{
    struct Node left = {25, NULL, NULL};
    struct Node right = {75, NULL, NULL};
    struct Node root = {50, &left, &right};

    if(search(&root, 75))
    {
        printf("Found\n");
    }
    else
    {
        printf("Not Found\n");
    }

    return 0;
}

Output: Found

Example 5: Advanced – Insert into a Binary Search Tree

#include <stdio.h>                      // Include standard input/output library
#include <stdlib.h>                     // Include memory allocation functions

struct Node
{
    int data;                           // Node value
    struct Node *left;                  // Left child
    struct Node *right;                 // Right child
};

struct Node *createNode(int value)      // Create a new node
{
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); // Allocate memory

    if(newNode == NULL)                 // Check allocation success
    {
        return NULL;                    // Allocation failed
    }

    newNode->data = value;              // Initialize node value
    newNode->left = NULL;               // No left child
    newNode->right = NULL;              // No right child

    return newNode;                     // Return new node
}

struct Node *insert(struct Node *root, int value) // Insert into BST
{
    if(root == NULL)                    // Empty position found
    {
        return createNode(value);       // Create new node
    }

    if(value < root->data)              // Go to left subtree
    {
        root->left = insert(root->left, value);
    }
    else if(value > root->data)         // Go to right subtree
    {
        root->right = insert(root->right, value);
    }

    return root;                        // Return unchanged root
}

int main()
{
    struct Node *root = NULL;           // Empty tree

    root = insert(root, 50);            // Insert nodes
    root = insert(root, 30);
    root = insert(root, 70);

    printf("Root = %d\n", root->data);  // Print root

    free(root->left);                   // Free allocated memory
    free(root->right);
    free(root);

    return 0;
}

Output: Root = 50

Common Mistakes and Pitfalls

Wrong	Correct
Forgetting to initialize child pointers	Set left and right to NULL
Ignoring malloc() failure	Always check if memory allocation succeeds
Forgetting to free allocated nodes	Free dynamically allocated memory when no longer needed
Traversing without checking NULL	Add a base case before accessing child nodes
Violating BST rules during insertion	Insert smaller values on the left and larger values on the right

Wrong:

root->left->data = 20;

Correct:

if(root->left != NULL)
{
    printf("%d", root->left->data);
}

Best Practices

Keep tree operations in separate functions.
Always initialize child pointers to NULL.
Validate memory allocation after every malloc() call.
Free all allocated nodes to avoid memory leaks.
Use recursion carefully to prevent excessive stack usage on very deep trees.
Balance trees when fast searching is important (for example, AVL or Red-Black Trees).
Use descriptive function names such as insert(), search(), deleteNode(), and traverseInorder().

When NOT to Use This

Avoid trees when:

The data is naturally sequential.
Fast random access by index is required.
The overhead of pointers is unnecessary.
A simple array or linked list is sufficient.
The dataset is very small and tree management adds unnecessary complexity.

Summary / Key Takeaways

Trees in C programming organize data hierarchically using nodes and edges.
A binary tree allows each node to have at most two children.
A Binary Search Tree (BST) stores smaller values on the left and larger values on the right.
Common traversals include preorder, inorder, postorder, and level-order.
Trees support efficient searching, insertion, and deletion compared to many linear structures.
Dynamic memory allocation is commonly used for creating tree nodes.
Always initialize pointers and free allocated memory.
Trees are widely used in databases, file systems, compilers, and search algorithms.

FAQ About Trees in C

1. What is a tree in C programming?

A tree is a hierarchical, non-linear data structure made up of nodes connected by edges. It is commonly used to represent hierarchical relationships and organize searchable data.

2. What is the difference between a binary tree and a binary search tree?

A binary tree allows each node to have at most two children without any ordering rules. A Binary Search Tree (BST) follows an ordering rule where values smaller than the parent are stored on the left, and larger values are stored on the right.

3. What are tree traversals?

Tree traversals are methods of visiting every node in a tree. The most common traversal methods are preorder, inorder, postorder, and level-order.

4. Why are trees better than linked lists for searching?

A balanced Binary Search Tree can perform searches in O(log n) time, while a linked list typically requires O(n) time because each node must be visited sequentially.

5. Where are trees used in real-world software?

Trees are widely used in file systems, database indexes, search engines, XML and HTML parsers, compiler syntax trees, decision trees in machine learning, routing algorithms, and auto-complete and dictionary applications.

Prev: Stacks and Queues Back to hub