October 17, 2026

Trees in C — Complete Data Structures and Algorithms Tutorial with Examples

SEO Title: Trees in C: Complete DSA Tutorial with Binary Tree, BST and Traversals

Suggested URL Slug: /trees-in-c/

Meta Description: Learn Trees in C with examples and programs. Understand tree terminology, binary trees, BST insertion, searching, deletion, inorder, preorder, postorder, level order traversal, AVL trees, and heaps.

Module 08: Trees in C

Introduction to Trees

A Tree is a non-linear data structure that organizes elements hierarchically. Unlike arrays and linked lists, which typically arrange elements sequentially, a tree connects elements through parent-child relationships.

Trees are used in file systems, databases, search algorithms, compiler design, networking, and priority queues.

For example, a company's organizational hierarchy can be represented as a tree: the CEO is at the top, managers report to the CEO, and employees report to managers.

1. Introduction to Trees

A tree consists of nodes connected by edges.

Consider this example:

          50
         /  \
       30    70
      / \    / \
     20 40  60 80

Here:

• 50 is the root node.

• 30 and 70 are children of 50.

• 20, 40, 60, and 80 are leaf nodes.

• The tree contains 7 nodes and 6 edges.

Why Are Trees Used?

Trees are useful when data has a hierarchy or when searching, insertion, and deletion can benefit from an organized structure.

Common applications include:

• File and folder hierarchies

• Database indexing

• Binary Search Trees

• Expression parsing

• Decision trees

• Priority queues using heaps

• Network routing and hierarchical data

2. Tree Terminology

Understanding tree terminology is essential before implementing tree algorithms.

Consider the following tree:

          A
         / \
        B   C
       / \
      D   E

Root: The topmost node. Here, A is the root.

Parent: A node that has one or more children. B is the parent of D and E.

Child: A node directly connected below another node. B and C are children of A.

Siblings: Nodes that share the same parent. B and C are siblings.

Leaf Node: A node with no children. C, D, and E are leaf nodes.

Internal Node: A node with at least one child. A and B are internal nodes.

Edge: A connection between two nodes.

Depth: The number of edges from the root to a node. The root has depth 0.

Height of a Node: The number of edges on the longest downward path from that node to a leaf. A leaf has height 0.

Height of a Tree: The height of the root. In this example, the tree height is 2.

Subtree: A node together with all its descendants.

Degree of a Node: The number of children that a node has.

Level: Often defined as depth plus one, making the root level 1. Some textbooks instead start the root at level 0, so check the convention being used.

3. Binary Tree

A Binary Tree is a tree in which each node has at most two children: a left child and a right child.

Example:

          10
         /  \
        20   30
       / \
      40  50

Node 10 has two children. Node 20 also has two children. Node 30 has no children.

Types of Binary Trees

Full Binary Tree: Every node has either zero or two children.

Complete Binary Tree: Every level is full except possibly the last, and the last level is filled from left to right.

Perfect Binary Tree: Every internal node has two children, and all leaves are at the same depth.

Skewed Binary Tree: Each internal node has only one child, producing a structure similar to a linked list.

Balanced Binary Tree: A tree whose height remains reasonably small relative to the number of nodes. The exact balance condition depends on the tree type.

Creating a Binary Tree Node in C

C does not provide a built-in tree data type. We can define one using a structure and pointers.

#include 
#include 

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

struct Node *createNode(int value) {
    struct Node *newNode = malloc(sizeof(struct Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;

    return newNode;
}

int main(void) {
    struct Node *root = createNode(10);

    root->left = createNode(20);
    root->right = createNode(30);

    printf("Root: %d\n", root->data);
    printf("Left child: %d\n", root->left->data);
    printf("Right child: %d\n", root->right->data);

    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Output:

Root: 10
Left child: 20
Right child: 30

The left and right pointers connect each node to its children. Setting a child pointer to NULL indicates that the node has no child on that side.

4. Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree that maintains an ordering rule:

• Values smaller than a node are placed in its left subtree.

• Values greater than a node are placed in its right subtree.

• In this tutorial, duplicate values are ignored.

Example:

          50
         /  \
       30    70
      / \    / \
     20 40  60 80

For node 50, all values in the left subtree are smaller than 50, and all values in the right subtree are greater than 50.

Binary Tree vs Binary Search Tree

A BST is not automatically balanced. Inserting sorted values into a basic BST can produce a skewed tree.

5. Tree Insertion and Searching

BST Insertion

To insert a value:

1. If the tree is empty, create the root.

2. If the new value is smaller, move left.

3. If the new value is larger, move right.

4. Repeat until an empty position is found.

5. Insert the new node at that position.

BST Searching

To search for a value:

1. Start at the root.

2. If the current node is NULL, the value is absent.

3. If the current node matches the target, return success.

4. If the target is smaller, search the left subtree.

5. Otherwise, search the right subtree.

C Program: BST Insertion and Searching

#include 
#include 

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

struct Node *createNode(int value) {
    struct Node *node = malloc(sizeof(struct Node));

    if (node == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    node->data = value;
    node->left = NULL;
    node->right = NULL;

    return node;
}

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 if (value > root->data) {
        root->right = insert(root->right, value);
    }

    return root;
}

struct Node *search(struct Node *root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }

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

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

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

void freeTree(struct Node *root) {
    if (root != NULL) {
        freeTree(root->left);
        freeTree(root->right);
        free(root);
    }
}

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

    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 70);
    root = insert(root, 20);
    root = insert(root, 40);

    printf("Inorder: ");
    inorder(root);

    if (search(root, 40) != NULL) {
        printf("\n40 found");
    } else {
        printf("\n40 not found");
    }

    if (search(root, 90) != NULL) {
        printf("\n90 found");
    } else {
        printf("\n90 not found");
    }

    printf("\n");
    freeTree(root);

    return 0;
}

Output:

Inorder: 20 30 40 50 70
40 found
90 not found

Insertion and searching take O(h) time, where h is the tree height. For a balanced BST, this is typically O(log n); for a skewed BST, it can be O(n).

6. Tree Deletion

Deleting a node from a BST requires maintaining the BST ordering property.

There are three main cases.

Case 1: Deleting a Leaf Node

A leaf node has no children. It can simply be removed.

Example: deleting 20.

Before:                 After:

      30                    30
     /  \                    \
   20   40                   40

Case 2: Deleting a Node with One Child

Replace the node with its only child.

Example: if 30 has only a right child 40, deleting 30 makes 40 take its place.

Case 3: Deleting a Node with Two Children

A common approach is to replace the node's value with its inorder successor, which is the smallest value in its right subtree, and then delete that successor node.

BST Deletion Program in C

Add the following functions to the BST code from the previous section:

struct Node *minValueNode(struct Node *node) {
    struct Node *current = node;

    while (current != NULL && current->left != NULL) {
        current = current->left;
    }

    return current;
}

struct Node *deleteNode(struct Node *root, int key) {
    if (root == NULL) {
        return NULL;
    }

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    } else {
        if (root->left == NULL) {
            struct Node *temp = root->right;
            free(root);
            return temp;
        }

        if (root->right == NULL) {
            struct Node *temp = root->left;
            free(root);
            return temp;
        }

        struct Node *temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

Example usage inside main():

root = deleteNode(root, 30);

printf("After deletion: ");
inorder(root);
printf("\n");

For the tree containing 50, 30, 70, 20, 40, deleting 30 replaces it with its inorder successor, 40.

Expected output:

After deletion: 20 40 50 70

The deletion operation takes O(h) time, where h is the height of the BST.

7. Inorder Traversal

Inorder Traversal visits nodes in this order:

1. Traverse the left subtree.

2. Visit the current node.

3. Traverse the right subtree.

The order is commonly written as Left → Root → Right.

For the BST:

          50
         /  \
       30    70
      / \    / \
     20 40  60 80

Inorder output:

20 30 40 50 60 70 80

In a BST, inorder traversal produces values in ascending order when the tree follows the standard ordering rule.

C Function

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

Time Complexity: O(n), because every node is visited once.

Auxiliary Space: O(h) for the recursive call stack, where h is tree height.

8. Preorder Traversal

Preorder Traversal visits nodes in this order:

1. Visit the current node.

2. Traverse the left subtree.

3. Traverse the right subtree.

The order is Root → Left → Right.

Using the same tree, the output is:

50 30 20 40 70 60 80

C Function

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

Preorder traversal is useful for serializing trees and creating copies of tree structures when combined with the required structural information.

Time Complexity: O(n).

Auxiliary Space: O(h) for the recursive call stack.

9. Postorder Traversal

Postorder Traversal visits nodes in this order:

1. Traverse the left subtree.

2. Traverse the right subtree.

3. Visit the current node.

The order is Left → Right → Root.

For the example tree, the output is:

20 40 30 60 80 70 50

C Function

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

Postorder traversal is useful when deleting a tree because child nodes can be freed before their parent.

Time Complexity: O(n).

Auxiliary Space: O(h) for the recursive call stack.

Inorder vs Preorder vs Postorder

10. Level Order Traversal

Level Order Traversal visits nodes level by level, starting at the root and proceeding from left to right at each level.

It uses a Queue to keep track of nodes waiting to be visited.

For the example tree, the output is:

50 30 70 20 40 60 80

Level Order Traversal in C

The following function assumes struct Node is defined as earlier.

#include 
#include 

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

    int capacity = 16;
    int front = 0;
    int rear = 0;

    struct Node **queue =
        malloc(capacity * sizeof(struct Node *));

    if (queue == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    queue[rear++] = root;

    while (front < rear) {
        struct Node *current = queue[front++];
        printf("%d ", current->data);

        if (current->left != NULL) {
            if (rear == capacity) {
                capacity *= 2;
                struct Node **temp =
                    realloc(queue, capacity * sizeof(struct Node *));

                if (temp == NULL) {
                    free(queue);
                    printf("\nMemory allocation failed\n");
                    return;
                }

                queue = temp;
            }

            queue[rear++] = current->left;
        }

        if (current->right != NULL) {
            if (rear == capacity) {
                capacity *= 2;
                struct Node **temp =
                    realloc(queue, capacity * sizeof(struct Node *));

                if (temp == NULL) {
                    free(queue);
                    printf("\nMemory allocation failed\n");
                    return;
                }

                queue = temp;
            }

            queue[rear++] = current->right;
        }
    }

    free(queue);
}

Example usage:

printf("Level Order: ");
levelOrder(root);
printf("\n");

Output:

Level Order: 50 30 70 20 40 60 80

This implementation dynamically grows its Queue. Its traversal time is O(n), and its auxiliary space is O(w), where w is the maximum number of nodes at any level.

11. AVL Tree Basics

An AVL Tree is a self-balancing Binary Search Tree. It automatically maintains a height-balance condition after insertions and deletions.

For every node, the balance factor is defined as:

[
\text{Balance Factor} = \text{Height(left)} - \text{Height(right)}
]

In an AVL Tree, each node's balance factor must be -1, 0, or +1.

If an insertion or deletion violates this condition, the tree performs rotations to restore balance.

Why Do We Need AVL Trees?

A normal BST can become skewed, causing searching to degrade to O(n). AVL balancing keeps the tree height O(log n), supporting O(log n) search, insertion, and deletion.

Four AVL Imbalance Cases

1. LL (Left-Left): A right rotation is required.

2. RR (Right-Right): A left rotation is required.

3. LR (Left-Right): A left rotation on the left child, followed by a right rotation.

4. RL (Right-Left): A right rotation on the right child, followed by a left rotation.

Example: Right Rotation

Before rotation:

       30
      /
     20
    /
   10

After a right rotation:

      20
     /  \
    10   30

The rotation restores balance while preserving the BST ordering property.

Basic Right Rotation in C

This function assumes the standard struct Node definition and a height field added to each node for AVL height tracking. It is a rotation primitive, not a complete AVL insertion implementation.

struct AVLNode {
    int data;
    int height;
    struct AVLNode *left;
    struct AVLNode *right;
};

int max(int a, int b) {
    return (a > b) ? a : b;
}

int height(struct AVLNode *node) {
    return node == NULL ? 0 : node->height;
}

struct AVLNode *rightRotate(struct AVLNode *y) {
    struct AVLNode *x = y->left;
    struct AVLNode *T2 = x->right;

    x->right = y;
    y->left = T2;

    y->height = 1 + max(height(y->left), height(y->right));
    x->height = 1 + max(height(x->left), height(x->right));

    return x;
}

For this height convention, a new leaf has height 1 and an empty subtree has height 0. A complete AVL implementation must also include node creation, balance-factor calculation, insertion/deletion logic, and all four rotation cases.

12. Heap Data Structure

A Heap is a specialized tree-based data structure that satisfies the heap property. Binary Heaps are usually implemented using arrays.

There are two common types:

Max Heap: Every parent is greater than or equal to its children. The maximum element is at the root.

Min Heap: Every parent is less than or equal to its children. The minimum element is at the root.

Example of a Max Heap:

          90
         /  \
       70    80
      / \    /
     20 40  60

The root 90 is greater than its children, and the property holds at every parent-child relationship.

Heap Array Representation

For a zero-based array, the index relationships are:

• Parent of index i: (i - 1) / 2, for i > 0

• Left child: 2 * i + 1

• Right child: 2 * i + 2

For example, the Max Heap above can be stored as:

[90, 70, 80, 20, 40, 60]

Max Heap Insertion in C

The following example demonstrates insertion into a Max Heap.

#include 

#define SIZE 100

int heap[SIZE];
int heapSize = 0;

void insertMaxHeap(int value) {
    if (heapSize == SIZE) {
        printf("Heap is full\n");
        return;
    }

    int i = heapSize;
    heap[heapSize++] = value;

    while (i > 0) {
        int parent = (i - 1) / 2;

        if (heap[parent] >= heap[i]) {
            break;
        }

        int temp = heap[parent];
        heap[parent] = heap[i];
        heap[i] = temp;

        i = parent;
    }
}

void displayHeap(void) {
    for (int i = 0; i < heapSize; i++) {
        printf("%d ", heap[i]);
    }
    printf("\n");
}

int main(void) {
    insertMaxHeap(40);
    insertMaxHeap(70);
    insertMaxHeap(20);
    insertMaxHeap(90);
    insertMaxHeap(60);

    printf("Max Heap array: ");
    displayHeap();

    return 0;
}

Output:

Max Heap array: 90 70 20 40 60

The exact array layout depends on insertion order, but the Max Heap property must always be maintained.

Heap Complexity

Heap vs Binary Search Tree

Tree Operations: Complexity Summary

Let n be the number of nodes and h be the tree height.

For a balanced BST, h is typically O(log n). For an ordinary, unbalanced BST, h can be O(n).

Real-World Applications of Trees

1. File Systems: Directories contain files and subdirectories.

2. Databases: Tree-based indexes support efficient data retrieval.

3. Compilers: Syntax trees represent program structure and expressions.

4. Search Systems: BSTs store and retrieve ordered values.

5. Priority Queues: Binary Heaps efficiently manage highest- or lowest-priority items.

6. Decision-Making: Decision trees model possible choices and outcomes.

7. Networking: Hierarchical structures help organize routing and management data.

8. Data Compression: Huffman Trees are used in Huffman coding.

Key Takeaways

• A Tree is a non-linear hierarchical data structure.

• A Binary Tree allows each node to have at most two children.

• A Binary Search Tree follows an ordering rule for left and right subtrees.

• BST insertion, search, and deletion depend on tree height.

• Inorder traversal of a standard BST returns values in sorted order.

• Preorder, postorder, and level order traversals visit nodes in different sequences.

• AVL Trees maintain balance through rotations.

• Binary Heaps support efficient priority-based operations.

• Trees are widely used in databases, compilers, file systems, and algorithms.

Conclusion

Trees are among the most important data structures in C and Data Structures & Algorithms. By understanding Binary Trees, Binary Search Trees, insertion, searching, deletion, traversals, AVL balancing, and Heaps, you build a strong foundation for advanced programming and algorithm design.

Compile and run the examples, experiment with different node values, and test edge cases such as empty trees, single-node trees, and skewed BSTs.