Trees

🌳 Trees in C: The Family Tree of Data

Once upon a time, in the land of computer memory, there lived data that wanted to be organized in a special way…

What is a Tree? 🤔

Imagine your family tree. You have grandparents at the top, then parents, then you and your siblings. A tree in programming works exactly the same way!

Simple Example:

• Your grandpa is at the TOP (we call him the root)
• His children (your parents, aunts, uncles) are below him
• You and your cousins are even lower

       Grandpa (Root)
         /    \
      Dad      Uncle
      /  \       |
    You  Sis  Cousin

That’s a tree! Data organized like a family.

🌲 Binary Tree Fundamentals

What Makes it “Binary”?

Binary = Two. Each parent can have at most 2 children.

Think of it like this:

• Your left hand = left child
• Your right hand = right child
• Each parent holds at most one thing in each hand!

The Building Block: A Node

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

Real-world example:

• data = A person’s name
• left = Their first child
• right = Their second child

Creating a Node

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

Key Tree Words

A Simple Binary Tree Example

int main() {
    // Create nodes
    struct Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);

    /*
        Tree looks like:
             10
            /  \
           5    15
    */
    return 0;
}

🚶 Tree Traversal Methods

The Big Question: How Do We Visit Everyone?

Imagine you’re visiting all your relatives in the family tree. What order do you go in?

There are 3 main ways:

1️⃣ In-Order Traversal (Left → Root → Right)

Story: First visit your left-side relatives, then yourself, then right-side relatives.

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

    inorder(node->left);    // Left first
    printf("%d ", node->data); // Then me
    inorder(node->right);   // Right last
}

Example Tree:

      4
     / \
    2   6
   / \
  1   3

In-Order Output: 1, 2, 3, 4, 6 (Sorted! Magic!)

2️⃣ Pre-Order Traversal (Root → Left → Right)

Story: Say hello to yourself first, then go left, then right.

void preorder(struct Node* node) {
    if (node == NULL) return;

    printf("%d ", node->data); // Me first!
    preorder(node->left);
    preorder(node->right);
}

Pre-Order Output: 4, 2, 1, 3, 6 (Parent first)

3️⃣ Post-Order Traversal (Left → Right → Root)

Story: Visit all your descendants first, then yourself last.

void postorder(struct Node* node) {
    if (node == NULL) return;

    postorder(node->left);
    postorder(node->right);
    printf("%d ", node->data); // Me last!
}

Post-Order Output: 1, 3, 2, 6, 4 (Parent last)

Quick Memory Trick 🧠

🔍 Binary Search Tree (BST)

The Superpower: Everything is Sorted!

A Binary Search Tree follows one magical rule:

LEFT is SMALLER, RIGHT is BIGGER

Example:

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

• Everything left of 50 is smaller (30, 20, 40)
• Everything right of 50 is bigger (70, 60, 80)

Why is this Amazing?

Looking for 60?

1. Start at 50. Is 60 bigger? Yes! Go RIGHT.
2. At 70. Is 60 smaller? Yes! Go LEFT.
3. Found 60! ✅

Only 3 steps instead of checking all 7 numbers!

Searching in BST

struct Node* search(struct Node* root,
                    int key) {
    // Base case: not found or found
    if (root == NULL ||
        root->data == key)
        return root;

    // Key is smaller - go left
    if (key < root->data)
        return search(root->left, key);

    // Key is bigger - go right
    return search(root->right, key);
}

Time Saved: Instead of checking every item, we cut the tree in half each time!

⚙️ BST Operations

1. INSERT: Adding a New Family Member

The Rule: Keep going left or right until you find an empty spot!

struct Node* insert(struct Node* node,
                    int key) {
    // Found an empty spot!
    if (node == NULL)
        return createNode(key);

    // Go left if smaller
    if (key < node->data)
        node->left =
            insert(node->left, key);
    // Go right if bigger
    else if (key > node->data)
        node->right =
            insert(node->right, key);

    return node;
}

Example: Insert 25 into our tree:

       50              50
      /  \    →       /  \
    30    70        30    70
   /              /  \
  20             20   25  ← New!

2. FIND MINIMUM: The Smallest Value

Keep going left until you can’t anymore!

struct Node* findMin(struct Node* node) {
    while (node->left != NULL)
        node = node->left;
    return node;
}

3. FIND MAXIMUM: The Largest Value

Keep going right until you can’t anymore!

struct Node* findMax(struct Node* node) {
    while (node->right != NULL)
        node = node->right;
    return node;
}

4. DELETE: Removing a Node

This is trickier! Three cases:

Case 1: Leaf Node (No children) Just remove it. Easy!

Case 2: One Child Replace the node with its child.

Case 3: Two Children Find the smallest in right subtree, replace, then delete that.

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

    // Find the node
    if (key < root->data)
        root->left =
            deleteNode(root->left, key);
    else if (key > root->data)
        root->right =
            deleteNode(root->right, key);
    else {
        // Found it! Now delete

        // Case 1 & 2: 0 or 1 child
        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;
        }

        // Case 3: Two children
        struct Node* temp =
            findMin(root->right);
        root->data = temp->data;
        root->right =
            deleteNode(root->right,
                       temp->data);
    }
    return root;
}

🎯 Complete Working Example

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

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

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

// Insert into BST
struct Node* insert(struct Node* node,
                    int key) {
    if (node == NULL)
        return createNode(key);

    if (key < node->data)
        node->left =
            insert(node->left, key);
    else
        node->right =
            insert(node->right, key);

    return node;
}

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

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

    // Build tree: 50, 30, 70, 20, 40
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);

    printf("In-order: ");
    inorder(root);
    // Output: 20 30 40 50 70

    return 0;
}

🌟 Why Trees Matter

💡 Key Takeaways

1. Binary Tree = Each node has at most 2 children
2. Traversals = Three ways to visit: In, Pre, Post
3. BST = Left is smaller, Right is bigger
4. Operations = Insert, Search, Delete - all use the left/right rule

You now understand trees! 🎉

From confused to confident - one tree at a time!