C Trees

A tree is a non-linear data structure where data is arranged in a hierarchical (parent-child) relationship. Unlike arrays, linked lists, stacks, and queues — which are linear — trees branch out like an actual tree in nature, making them ideal for representing hierarchical data.

Trees are used everywhere: file systems, databases, compilers, and search engines all rely on tree structures internally.

Tree Terminology

            [10]          <-- Root (top-most node, no parent)
           /    \
        [6]      [15]     <-- Children of root, Internal nodes
        / \      /  \
      [3] [8] [12]  [20]  <-- Leaf nodes (no children)

Root     : 10  (first node, no parent)
Leaf     : 3, 8, 12, 20  (no children)
Parent   : 10 is parent of 6 and 15
Children : 6 and 15 are children of 10
Height   : 3 levels deep (root at level 1)
Subtree  : 6, 3, 8 form a subtree rooted at 6

Binary Tree

A binary tree is the most common tree type. Each node has at most two children — a left child and a right child.

Node Structure in C

struct Node {
    int data;
    struct Node *left;    // pointer to left child
    struct Node *right;   // pointer to right child
};

Creating a Node

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

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

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

Binary Search Tree (BST)

A Binary Search Tree (BST) is a binary tree with a special rule:

• All values in the left subtree are less than the root
• All values in the right subtree are greater than the root
• This rule applies to every node recursively

Insert: 10, 6, 15, 3, 8, 12, 20

         [10]
        /    \
      [6]    [15]
      / \    /  \
    [3] [8][12] [20]

Left of 10: 6 (less than 10) ✓
Right of 10: 15 (greater than 10) ✓
Left of 6: 3 (less than 6) ✓
Right of 6: 8 (greater than 6, less than 10) ✓

BST Insert Operation

struct Node* insert(struct Node *root, int value)
{
    if (root == NULL)                   // empty spot found — place node here
        return createNode(value);

    if (value < root->data)
        root->left  = insert(root->left,  value);   // go left
    else if (value > root->data)
        root->right = insert(root->right, value);   // go right

    return root;   // node already exists — skip duplicate
}

BST Search Operation

struct Node* search(struct Node *root, int value)
{
    if (root == NULL)            return NULL;   // not found
    if (value == root->data)    return root;   // found!
    if (value <  root->data)    return search(root->left,  value);
    return                              search(root->right, value);
}

Search Visual

Search for 8 in BST:

Start at root [10] — 8 < 10 → go LEFT
At [6] — 8 > 6 → go RIGHT
At [8] — 8 == 8 → FOUND! ✓

Only 3 comparisons to find 8 in a 7-node tree.

Tree Traversals

Traversal means visiting every node in the tree in a specific order. There are three main traversal methods for binary trees.

1. In-Order Traversal (Left → Root → Right)

In-order traversal of a BST always produces values in sorted (ascending) order.

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

For the BST above: 3 6 8 10 12 15 20 (sorted!)

2. Pre-Order Traversal (Root → Left → Right)

Used to copy or serialize a tree structure.

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

Output: 10 6 3 8 15 12 20

3. Post-Order Traversal (Left → Right → Root)

Used to delete a tree safely (children freed before parent).

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

Output: 3 8 6 12 20 15 10

Traversal Summary Diagram

Tree:          [10]
              /    \
           [6]      [15]
           / \      /  \
         [3] [8] [12]  [20]

In-Order   (L Root R): 3  6  8  10 12 15 20  ← sorted order
Pre-Order  (Root L R): 10  6  3  8 15 12 20  ← root first
Post-Order (L R Root): 3  8  6 12 20 15 10   ← root last

Complete BST Program

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

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

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

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

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

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

    root = insert(root, 10);
    root = insert(root, 6);
    root = insert(root, 15);
    root = insert(root, 3);
    root = insert(root, 8);
    root = insert(root, 12);
    root = insert(root, 20);

    printf("In-Order: ");
    inOrder(root);   // Output: 3 6 8 10 12 15 20
    printf("\n");

    return 0;
}

Finding Height of a Tree

int height(struct Node *root)
{
    if (root == NULL) return 0;
    int leftH  = height(root->left);
    int rightH = height(root->right);
    return 1 + (leftH > rightH ? leftH : rightH);
}

Real-World Uses of Trees

Summary

A tree is a hierarchical data structure made of nodes connected by edges. Each node contains data and pointers to its children. A binary tree allows each node to have at most two children. A Binary Search Tree (BST) adds the rule that left child values are smaller and right child values are larger than the parent, enabling fast search. Three traversal methods — in-order, pre-order, and post-order — visit nodes in different sequences for different purposes. In-order traversal of a BST always yields a sorted sequence. Trees are foundational to file systems, database engines, compilers, and search algorithms used in modern software.