Trees and Binary Trees in C

A binary tree is a tree where each node has at most two children, referred to as the left child and right child. Binary trees are the foundation for many important data structures including binary search trees, heaps, and expression trees.

Binary Tree Node Structure

// Binary tree node structure
typedef struct TreeNode {
    int data;
    struct TreeNode *left;   // Pointer to left child
    struct TreeNode *right;  // Pointer to right child
} TreeNode;

// Visual representation:
//
//        [data]
//        /    \
//    left      right
//      ↓         ↓
//   [child]   [child]
//     or        or
//    NULL      NULL

Types of Binary Trees

// 1. Full Binary Tree: Every node has 0 or 2 children
//         1
//        / \
//       2   3
//      / \
//     4   5

// 2. Complete Binary Tree: All levels filled except possibly last,
//    which is filled from left to right
//         1
//        / \
//       2   3
//      / \  /
//     4  5 6

// 3. Perfect Binary Tree: All internal nodes have 2 children,
//    all leaves at same level
//         1
//        / \
//       2   3
//      / \ / \
//     4  5 6  7

// 4. Balanced Binary Tree: Height difference between left and right
//    subtrees is at most 1 for every node

// 5. Degenerate (Skewed) Tree: Each parent has only one child
//    (essentially a linked list)
//     1
//      \
//       2
//        \
//         3

Binary Tree Implementation

// binary_tree.h
#ifndef BINARY_TREE_H
#define BINARY_TREE_H

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Function prototypes
TreeNode *createNode(int data);
TreeNode *insertLeft(TreeNode *parent, int data);
TreeNode *insertRight(TreeNode *parent, int data);
void freeTree(TreeNode *root);
int countNodes(TreeNode *root);
int treeHeight(TreeNode *root);
bool isLeaf(TreeNode *node);

#endif

// binary_tree.c
#include "binary_tree.h"

// Create a new node
TreeNode *createNode(int data) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Insert as left child
TreeNode *insertLeft(TreeNode *parent, int data) {
    if (parent == NULL) {
        printf("Parent is NULL!\n");
        return NULL;
    }
    parent->left = createNode(data);
    return parent->left;
}

// Insert as right child
TreeNode *insertRight(TreeNode *parent, int data) {
    if (parent == NULL) {
        printf("Parent is NULL!\n");
        return NULL;
    }
    parent->right = createNode(data);
    return parent->right;
}

// Free entire tree (post-order deletion)
void freeTree(TreeNode *root) {
    if (root == NULL) return;
    
    freeTree(root->left);   // Free left subtree
    freeTree(root->right);  // Free right subtree
    free(root);             // Free current node
}

// Count total nodes
int countNodes(TreeNode *root) {
    if (root == NULL) return 0;
    
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// Calculate height of tree
int treeHeight(TreeNode *root) {
    if (root == NULL) return -1;  // Empty tree has height -1
    
    int leftHeight = treeHeight(root->left);
    int rightHeight = treeHeight(root->right);
    
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

// Check if node is a leaf
bool isLeaf(TreeNode *node) {
    return (node != NULL && node->left == NULL && node->right == NULL);
}

Building a Binary Tree

// main.c - Building and using a binary tree
#include "binary_tree.h"

int main() {
    // Build this tree:
    //        1
    //       / \
    //      2   3
    //     / \   \
    //    4   5   6
    
    TreeNode *root = createNode(1);
    
    TreeNode *node2 = insertLeft(root, 2);
    TreeNode *node3 = insertRight(root, 3);
    
    insertLeft(node2, 4);
    insertRight(node2, 5);
    insertRight(node3, 6);
    
    printf("Number of nodes: %d\n", countNodes(root));  // 6
    printf("Height of tree: %d\n", treeHeight(root));   // 2
    printf("Is root a leaf? %s\n", isLeaf(root) ? "Yes" : "No");  // No
    printf("Is node 4 a leaf? %s\n", isLeaf(node2->left) ? "Yes" : "No");  // Yes
    
    // Clean up
    freeTree(root);
    
    return 0;
}

int countLeaves(TreeNode *root) {
    if (root == NULL) return 0;
    
    // If leaf node
    if (root->left == NULL && root->right == NULL) {
        return 1;
    }
    
    // Count leaves in left and right subtrees
    return countLeaves(root->left) + countLeaves(root->right);
}

// Example:
//        1
//       / \
//      2   3
//     / \   \
//    4   5   6
// countLeaves returns 3 (nodes 4, 5, 6)

void mirrorTree(TreeNode *root) {
    if (root == NULL) return;
    
    // Swap left and right children
    TreeNode *temp = root->left;
    root->left = root->right;
    root->right = temp;
    
    // Recursively mirror subtrees
    mirrorTree(root->left);
    mirrorTree(root->right);
}

// Before:        After (mirror):
//     1              1
//    / \            / \
//   2   3          3   2
//  / \              / \
// 4   5            5   4

A Binary Search Tree (BST) is a binary tree with a special ordering property: for every node, all values in its left subtree are smaller, and all values in its right subtree are larger. This property enables efficient searching, insertion, and deletion with average O(log n) time complexity.

BST Visualization

// Valid BST:
//           50
//          /  \
//        30    70
//       / \    / \
//      20 40  60 80
//
// For node 50: left subtree (20,30,40) < 50 < right subtree (60,70,80) ✓
// For node 30: 20 < 30 < 40 ✓
// For node 70: 60 < 70 < 80 ✓

// NOT a valid BST:
//           50
//          /  \
//        30    70
//       / \      \
//      20 60    80   ← 60 is in left subtree of 50 but 60 > 50!

BST Implementation

// bst.h
#ifndef BST_H
#define BST_H

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

typedef struct BSTNode {
    int data;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

BSTNode *createBSTNode(int data);
BSTNode *insertBST(BSTNode *root, int data);
BSTNode *searchBST(BSTNode *root, int key);
BSTNode *findMin(BSTNode *root);
BSTNode *findMax(BSTNode *root);
BSTNode *deleteBST(BSTNode *root, int key);
bool isBST(BSTNode *root, int min, int max);

#endif

// bst.c
#include "bst.h"
#include <limits.h>

// Create a new BST node
BSTNode *createBSTNode(int data) {
    BSTNode *newNode = (BSTNode *)malloc(sizeof(BSTNode));
    if (newNode == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Insert a value into BST - O(log n) average, O(n) worst
BSTNode *insertBST(BSTNode *root, int data) {
    // Base case: empty tree or reached insertion point
    if (root == NULL) {
        return createBSTNode(data);
    }
    
    // Recursive case: traverse to correct position
    if (data < root->data) {
        root->left = insertBST(root->left, data);
    } else if (data > root->data) {
        root->right = insertBST(root->right, data);
    }
    // If data == root->data, ignore duplicate (or handle as needed)
    
    return root;
}

// Search for a value - O(log n) average, O(n) worst
BSTNode *searchBST(BSTNode *root, int key) {
    // Base cases: empty tree or found
    if (root == NULL || root->data == key) {
        return root;
    }
    
    // Key is smaller, search left subtree
    if (key < root->data) {
        return searchBST(root->left, key);
    }
    
    // Key is larger, search right subtree
    return searchBST(root->right, key);
}

// Find minimum value (leftmost node) - O(log n)
BSTNode *findMin(BSTNode *root) {
    if (root == NULL) return NULL;
    
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}

// Find maximum value (rightmost node) - O(log n)
BSTNode *findMax(BSTNode *root) {
    if (root == NULL) return NULL;
    
    while (root->right != NULL) {
        root = root->right;
    }
    return root;
}

// Delete a value from BST - O(log n) average
BSTNode *deleteBST(BSTNode *root, int key) {
    if (root == NULL) return NULL;
    
    // Find the node to delete
    if (key < root->data) {
        root->left = deleteBST(root->left, key);
    } else if (key > root->data) {
        root->right = deleteBST(root->right, key);
    } else {
        // Found the node to delete
        
        // Case 1: Leaf node (no children)
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }
        
        // Case 2: One child
        if (root->left == NULL) {
            BSTNode *temp = root->right;
            free(root);
            return temp;
        }
        if (root->right == NULL) {
            BSTNode *temp = root->left;
            free(root);
            return temp;
        }
        
        // Case 3: Two children
        // Find inorder successor (smallest in right subtree)
        BSTNode *successor = findMin(root->right);
        root->data = successor->data;
        root->right = deleteBST(root->right, successor->data);
    }
    
    return root;
}

// Verify if tree is a valid BST
bool isBST(BSTNode *root, int min, int max) {
    if (root == NULL) return true;
    
    // Check current node
    if (root->data <= min || root->data >= max) {
        return false;
    }
    
    // Check subtrees with updated bounds
    return isBST(root->left, min, root->data) &&
           isBST(root->right, root->data, max);
}

// Wrapper function
bool isValidBST(BSTNode *root) {
    return isBST(root, INT_MIN, INT_MAX);
}

Using the BST

int main() {
    BSTNode *root = NULL;
    
    // Insert values
    root = insertBST(root, 50);
    root = insertBST(root, 30);
    root = insertBST(root, 70);
    root = insertBST(root, 20);
    root = insertBST(root, 40);
    root = insertBST(root, 60);
    root = insertBST(root, 80);
    
    // Tree structure:
    //           50
    //          /  \
    //        30    70
    //       / \    / \
    //      20 40  60 80
    
    // Search
    BSTNode *found = searchBST(root, 40);
    if (found) printf("Found: %d\n", found->data);  // Found: 40
    
    // Find min and max
    printf("Min: %d\n", findMin(root)->data);  // Min: 20
    printf("Max: %d\n", findMax(root)->data);  // Max: 80
    
    // Delete
    root = deleteBST(root, 30);  // Delete node with two children
    // Now tree:
    //           50
    //          /  \
    //        40    70
    //       /     / \
    //      20    60 80
    
    return 0;
}

BSTNode *inorderSuccessor(BSTNode *root, BSTNode *node) {
    // Case 1: Node has right subtree
    // Successor is the minimum in right subtree
    if (node->right != NULL) {
        return findMin(node->right);
    }
    
    // Case 2: No right subtree
    // Successor is the nearest ancestor for which
    // the given node is in its left subtree
    BSTNode *successor = NULL;
    while (root != NULL) {
        if (node->data < root->data) {
            successor = root;  // Potential successor
            root = root->left;
        } else if (node->data > root->data) {
            root = root->right;
        } else {
            break;  // Found the node
        }
    }
    
    return successor;
}

// Example:
//           50
//          /  \
//        30    70
//       / \   
//      20 40  
// Inorder successor of 30 is 40 (min in right subtree)
// Inorder successor of 40 is 50 (ancestor)

// Using inorder traversal (gives sorted order in BST)
int kthSmallest(BSTNode *root, int k, int *count) {
    if (root == NULL) return -1;
    
    // Search in left subtree
    int result = kthSmallest(root->left, k, count);
    if (result != -1) return result;  // Found in left
    
    // Process current node
    (*count)++;
    if (*count == k) return root->data;
    
    // Search in right subtree
    return kthSmallest(root->right, k, count);
}

// Wrapper function
int findKthSmallest(BSTNode *root, int k) {
    int count = 0;
    return kthSmallest(root, k, &count);
}

// Example:
//           50
//          /  \
//        30    70
//       / \   
//      20 40  
// Inorder: 20, 30, 40, 50, 70
// 1st smallest: 20
// 3rd smallest: 40

Tree traversal is the process of visiting every node in a tree exactly once. The three main depth-first traversals differ in when the root is processed relative to its subtrees. Level-order traversal (BFS) visits nodes level by level.

Traversal Types Overview

// Example tree for all traversals:
//           1
//          / \
//         2   3
//        / \   \
//       4   5   6

// Inorder (Left, Root, Right):    4, 2, 5, 1, 3, 6
// Preorder (Root, Left, Right):   1, 2, 4, 5, 3, 6
// Postorder (Left, Right, Root):  4, 5, 2, 6, 3, 1
// Level-order (BFS):              1, 2, 3, 4, 5, 6

Inorder Traversal (Left → Root → Right)

// Inorder traversal - For BST, gives sorted order!
void inorder(TreeNode *root) {
    if (root == NULL) return;
    
    inorder(root->left);         // Visit left subtree
    printf("%d ", root->data);   // Process root
    inorder(root->right);        // Visit right subtree
}

// Iterative version using stack
void inorderIterative(TreeNode *root) {
    TreeNode *stack[100];
    int top = -1;
    TreeNode *current = root;
    
    while (current != NULL || top >= 0) {
        // Go to leftmost node
        while (current != NULL) {
            stack[++top] = current;
            current = current->left;
        }
        
        // Process and go right
        current = stack[top--];
        printf("%d ", current->data);
        current = current->right;
    }
}

Preorder Traversal (Root → Left → Right)

// Preorder traversal - Useful for copying trees
void preorder(TreeNode *root) {
    if (root == NULL) return;
    
    printf("%d ", root->data);   // Process root first
    preorder(root->left);        // Visit left subtree
    preorder(root->right);       // Visit right subtree
}

// Iterative version using stack
void preorderIterative(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *stack[100];
    int top = -1;
    stack[++top] = root;
    
    while (top >= 0) {
        TreeNode *node = stack[top--];
        printf("%d ", node->data);
        
        // Push right first so left is processed first
        if (node->right) stack[++top] = node->right;
        if (node->left) stack[++top] = node->left;
    }
}

Postorder Traversal (Left → Right → Root)

// Postorder traversal - Useful for deleting trees
void postorder(TreeNode *root) {
    if (root == NULL) return;
    
    postorder(root->left);       // Visit left subtree
    postorder(root->right);      // Visit right subtree
    printf("%d ", root->data);   // Process root last
}

// Why postorder for deletion?
// Children must be deleted before parent to avoid memory leaks
void deleteTree(TreeNode *root) {
    if (root == NULL) return;
    
    deleteTree(root->left);   // Delete left subtree first
    deleteTree(root->right);  // Delete right subtree
    printf("Deleting %d\n", root->data);
    free(root);               // Now safe to delete root
}

Level-Order Traversal (BFS)

// Level-order traversal using queue
void levelOrder(TreeNode *root) {
    if (root == NULL) return;
    
    // Simple queue implementation
    TreeNode *queue[100];
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    
    while (front < rear) {
        TreeNode *node = queue[front++];
        printf("%d ", node->data);
        
        // Enqueue children
        if (node->left) queue[rear++] = node->left;
        if (node->right) queue[rear++] = node->right;
    }
}

// Level-order with level separation
void levelOrderWithLevels(TreeNode *root) {
    if (root == NULL) return;
    
    TreeNode *queue[100];
    int front = 0, rear = 0;
    
    queue[rear++] = root;
    int level = 0;
    
    while (front < rear) {
        int levelSize = rear - front;  // Nodes at current level
        printf("Level %d: ", level);
        
        for (int i = 0; i < levelSize; i++) {
            TreeNode *node = queue[front++];
            printf("%d ", node->data);
            
            if (node->left) queue[rear++] = node->left;
            if (node->right) queue[rear++] = node->right;
        }
        printf("\n");
        level++;
    }
}

// Output:
// Level 0: 1
// Level 1: 2 3
// Level 2: 4 5 6

Traversal Comparison

//         A
//        / \
//       B   C
//      /   / \
//     D   E   F

// Inorder (L-Root-R):   D, B, A, E, C, F
// Preorder (Root-L-R):  A, B, D, C, E, F
// Postorder (L-R-Root): D, B, E, F, C, A
// Level-order (BFS):    A, B, C, D, E, F

// Algorithm:
// 1. First element of preorder is always root → A
// 2. Find A in inorder: [D,B,E] | A | [F,C]
//    - Left subtree has elements: D,B,E
//    - Right subtree has elements: F,C
// 3. Next preorder element B is root of left subtree
// 4. Find B in inorder: [D] | B | [E]
// 5. Continue recursively...

// Result:
//         A
//        / \
//       B   C
//      / \  /
//     D   E F

TreeNode *buildTree(int *inorder, int *preorder, 
                    int inStart, int inEnd, int *preIndex) {
    if (inStart > inEnd) return NULL;
    
    TreeNode *node = createNode(preorder[*preIndex]);
    (*preIndex)++;
    
    if (inStart == inEnd) return node;
    
    // Find index of current root in inorder
    int inIndex;
    for (inIndex = inStart; inIndex <= inEnd; inIndex++) {
        if (inorder[inIndex] == node->data) break;
    }
    
    node->left = buildTree(inorder, preorder, inStart, inIndex-1, preIndex);
    node->right = buildTree(inorder, preorder, inIndex+1, inEnd, preIndex);
    
    return node;
}

Beyond basic traversals, trees support many useful operations including finding the lowest common ancestor, checking tree properties, and calculating various metrics.

Lowest Common Ancestor (LCA)

// Find LCA in a Binary Tree
TreeNode *findLCA(TreeNode *root, int n1, int n2) {
    if (root == NULL) return NULL;
    
    // If either n1 or n2 matches root, root is LCA
    if (root->data == n1 || root->data == n2) {
        return root;
    }
    
    // Look for nodes in left and right subtrees
    TreeNode *leftLCA = findLCA(root->left, n1, n2);
    TreeNode *rightLCA = findLCA(root->right, n1, n2);
    
    // If both return non-NULL, root is LCA
    if (leftLCA && rightLCA) return root;
    
    // Otherwise, return non-NULL child
    return leftLCA ? leftLCA : rightLCA;
}

// LCA in BST (more efficient using BST property)
BSTNode *findLCAinBST(BSTNode *root, int n1, int n2) {
    if (root == NULL) return NULL;
    
    // If both n1 and n2 are smaller, LCA is in left subtree
    if (n1 < root->data && n2 < root->data) {
        return findLCAinBST(root->left, n1, n2);
    }
    
    // If both are larger, LCA is in right subtree
    if (n1 > root->data && n2 > root->data) {
        return findLCAinBST(root->right, n1, n2);
    }
    
    // Otherwise, we're at the split point (or one matches)
    return root;
}

Check if Two Trees are Identical

bool areIdentical(TreeNode *root1, TreeNode *root2) {
    // Both empty
    if (root1 == NULL && root2 == NULL) return true;
    
    // One empty, one not
    if (root1 == NULL || root2 == NULL) return false;
    
    // Check current nodes and subtrees
    return (root1->data == root2->data) &&
           areIdentical(root1->left, root2->left) &&
           areIdentical(root1->right, root2->right);
}

Check if Tree is Balanced

// A tree is balanced if height difference of subtrees <= 1
// for every node

int checkBalance(TreeNode *root) {
    if (root == NULL) return 0;
    
    int leftHeight = checkBalance(root->left);
    if (leftHeight == -1) return -1;  // Left subtree unbalanced
    
    int rightHeight = checkBalance(root->right);
    if (rightHeight == -1) return -1;  // Right subtree unbalanced
    
    // Check current node's balance
    if (abs(leftHeight - rightHeight) > 1) {
        return -1;  // Unbalanced
    }
    
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

bool isBalanced(TreeNode *root) {
    return checkBalance(root) != -1;
}

Path Sum Problems

// Check if path with given sum exists (root to leaf)
bool hasPathSum(TreeNode *root, int targetSum) {
    if (root == NULL) return false;
    
    // Subtract current node's value
    targetSum -= root->data;
    
    // If leaf node, check if sum is 0
    if (root->left == NULL && root->right == NULL) {
        return targetSum == 0;
    }
    
    // Check left or right subtree
    return hasPathSum(root->left, targetSum) ||
           hasPathSum(root->right, targetSum);
}

// Print all root-to-leaf paths
void printPaths(TreeNode *root, int path[], int pathLen) {
    if (root == NULL) return;
    
    // Add current node to path
    path[pathLen++] = root->data;
    
    // If leaf, print path
    if (root->left == NULL && root->right == NULL) {
        printf("Path: ");
        for (int i = 0; i < pathLen; i++) {
            printf("%d ", path[i]);
        }
        printf("\n");
    } else {
        // Continue to children
        printPaths(root->left, path, pathLen);
        printPaths(root->right, path, pathLen);
    }
}

// Wrapper
void printAllPaths(TreeNode *root) {
    int path[100];
    printPaths(root, path, 0);
}

Diameter of Tree

// Diameter: longest path between any two nodes
// May or may not pass through root

int diameterHelper(TreeNode *root, int *diameter) {
    if (root == NULL) return 0;
    
    int leftHeight = diameterHelper(root->left, diameter);
    int rightHeight = diameterHelper(root->right, diameter);
    
    // Update diameter if path through this node is longer
    *diameter = (*diameter > leftHeight + rightHeight) ? 
                *diameter : leftHeight + rightHeight;
    
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int treeDiameter(TreeNode *root) {
    int diameter = 0;
    diameterHelper(root, &diameter);
    return diameter;
}

// Example:
//           1
//          / \
//         2   3
//        / \
//       4   5
// Diameter = 3 (path: 4 → 2 → 1 → 3 or 5 → 2 → 1 → 3)

Time Complexity Summary

*Binary tree insert at known position. BST worst case occurs with skewed tree (essentially a linked list).

int maxPathSumToLeaf(TreeNode *root) {
    if (root == NULL) return 0;
    
    // If leaf node
    if (root->left == NULL && root->right == NULL) {
        return root->data;
    }
    
    // Get max sum from left and right subtrees
    int leftSum = INT_MIN, rightSum = INT_MIN;
    
    if (root->left) {
        leftSum = maxPathSumToLeaf(root->left);
    }
    if (root->right) {
        rightSum = maxPathSumToLeaf(root->right);
    }
    
    // Return max of left/right plus current
    return root->data + (leftSum > rightSum ? leftSum : rightSum);
}

// Example:
//         10
//        /  \
//       2    10
//      / \     \
//     20  1    -25
// Max path sum: 10 → 2 → 20 = 32

// Serialize using preorder (root first)
void serialize(BSTNode *root, char *buffer, int *index) {
    if (root == NULL) {
        buffer[(*index)++] = '#';  // Null marker
        buffer[(*index)++] = ',';
        return;
    }
    
    *index += sprintf(buffer + *index, "%d,", root->data);
    serialize(root->left, buffer, index);
    serialize(root->right, buffer, index);
}

// Deserialize
BSTNode *deserializeHelper(char **str) {
    if (**str == '#') {
        (*str) += 2;  // Skip '#,'
        return NULL;
    }
    
    int val = 0;
    while (**str != ',') {
        val = val * 10 + (**str - '0');
        (*str)++;
    }
    (*str)++;  // Skip ','
    
    BSTNode *node = createBSTNode(val);
    node->left = deserializeHelper(str);
    node->right = deserializeHelper(str);
    
    return node;
}

BSTNode *deserialize(char *buffer) {
    return deserializeHelper(&buffer);
}

// Example:
//     5
//    / \
//   3   7
// Serialized: "5,3,#,#,7,#,#,"

An unbalanced BST can degrade to O(n) operations. Tree balancing techniques ensure the tree maintains a height of O(log n), guaranteeing efficient operations. Self-balancing trees automatically restructure during insertions and deletions.

Balance Factor

// Balance Factor = Height(left subtree) - Height(right subtree)
// For a balanced tree: -1 <= Balance Factor <= 1

int getBalanceFactor(TreeNode *node) {
    if (node == NULL) return 0;
    return treeHeight(node->left) - treeHeight(node->right);
}

// Balanced tree (BF = 0, -1, or 1 for all nodes):
//         50 (BF=0)
//        /  \
//      30    70 (BF=0)
//     /       \
//    20       80

// Unbalanced tree (BF = 2 at root):
//         50 (BF=2)
//        /
//      30 (BF=1)
//     /
//    20 (BF=0)

Tree Rotations

// Rotations are the fundamental operations for balancing
// They restructure the tree while maintaining BST property

// Right Rotation (for left-heavy trees)
//       y                x
//      / \             /   \
//     x   T3   -->    T1    y
//    / \                   / \
//   T1 T2                 T2 T3

TreeNode *rightRotate(TreeNode *y) {
    TreeNode *x = y->left;
    TreeNode *T2 = x->right;
    
    // Perform rotation
    x->right = y;
    y->left = T2;
    
    return x;  // New root of subtree
}

// Left Rotation (for right-heavy trees)
//     x                    y
//    / \                 /   \
//   T1  y     -->       x    T3
//      / \             / \
//     T2 T3           T1 T2

TreeNode *leftRotate(TreeNode *x) {
    TreeNode *y = x->right;
    TreeNode *T2 = y->left;
    
    // Perform rotation
    y->left = x;
    x->right = T2;
    
    return y;  // New root of subtree
}

AVL Tree Insertion (Self-Balancing)

// AVL Tree: Self-balancing BST where balance factor is always -1, 0, or 1

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

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

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

AVLNode *createAVLNode(int data) {
    AVLNode *node = (AVLNode *)malloc(sizeof(AVLNode));
    node->data = data;
    node->left = node->right = NULL;
    node->height = 1;  // New node starts at height 1
    return node;
}

// AVL Insert with automatic balancing
AVLNode *insertAVL(AVLNode *node, int data) {
    // 1. Standard BST insertion
    if (node == NULL) return createAVLNode(data);
    
    if (data < node->data)
        node->left = insertAVL(node->left, data);
    else if (data > node->data)
        node->right = insertAVL(node->right, data);
    else
        return node;  // Duplicates not allowed
    
    // 2. Update height
    node->height = 1 + max(height(node->left), height(node->right));
    
    // 3. Get balance factor
    int balance = height(node->left) - height(node->right);
    
    // 4. Handle 4 unbalanced cases
    
    // Left Left Case (right rotate)
    if (balance > 1 && data < node->left->data)
        return rightRotate(node);
    
    // Right Right Case (left rotate)
    if (balance < -1 && data > node->right->data)
        return leftRotate(node);
    
    // Left Right Case (left-right rotate)
    if (balance > 1 && data > node->left->data) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }
    
    // Right Left Case (right-left rotate)
    if (balance < -1 && data < node->right->data) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }
    
    return node;  // Return unchanged node
}

Types of Self-Balancing Trees

Trees are fundamental data structures used extensively in computer science. From organizing file systems to powering search engines, trees provide efficient hierarchical organization and fast operations.

1. Expression Trees

// Expression trees represent arithmetic expressions
// Leaves are operands, internal nodes are operators

// Expression: (3 + 5) * (2 - 1)
//           *
//          / \
//         +   -
//        / \ / \
//       3  5 2  1

typedef struct ExprNode {
    char op;        // Operator or '\0' if operand
    int value;      // Value if operand
    struct ExprNode *left;
    struct ExprNode *right;
} ExprNode;

// Evaluate expression tree (postorder)
int evaluate(ExprNode *root) {
    if (root == NULL) return 0;
    
    // Leaf node (operand)
    if (root->left == NULL && root->right == NULL) {
        return root->value;
    }
    
    // Internal node (operator)
    int leftVal = evaluate(root->left);
    int rightVal = evaluate(root->right);
    
    switch (root->op) {
        case '+': return leftVal + rightVal;
        case '-': return leftVal - rightVal;
        case '*': return leftVal * rightVal;
        case '/': return leftVal / rightVal;
    }
    return 0;
}

2. File System Representation

// File systems are tree structures
// Directories are internal nodes, files are leaves

typedef struct FileNode {
    char name[256];
    int isDirectory;           // 1 = directory, 0 = file
    long size;                 // File size in bytes
    struct FileNode *firstChild;  // First child (for directories)
    struct FileNode *nextSibling; // Next sibling
} FileNode;

// Print directory tree structure
void printTree(FileNode *node, int depth) {
    if (node == NULL) return;
    
    // Print indentation
    for (int i = 0; i < depth; i++) printf("  ");
    
    if (node->isDirectory) {
        printf("[DIR] %s/\n", node->name);
        printTree(node->firstChild, depth + 1);
    } else {
        printf("%s (%ld bytes)\n", node->name, node->size);
    }
    
    printTree(node->nextSibling, depth);
}

// Output:
// [DIR] root/
//   [DIR] documents/
//     report.txt (1024 bytes)
//     notes.pdf (2048 bytes)
//   [DIR] images/
//     photo.jpg (50000 bytes)

3. Autocomplete / Trie (Prefix Tree)

// Trie: Tree for efficient prefix-based search
// Used in autocomplete, spell checkers, IP routing

#define ALPHABET_SIZE 26

typedef struct TrieNode {
    struct TrieNode *children[ALPHABET_SIZE];
    bool isEndOfWord;
} TrieNode;

TrieNode *createTrieNode() {
    TrieNode *node = (TrieNode *)malloc(sizeof(TrieNode));
    node->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        node->children[i] = NULL;
    return node;
}

// Insert word into trie
void insertTrie(TrieNode *root, const char *word) {
    TrieNode *current = root;
    
    while (*word) {
        int index = *word - 'a';
        if (current->children[index] == NULL)
            current->children[index] = createTrieNode();
        current = current->children[index];
        word++;
    }
    current->isEndOfWord = true;
}

// Search for word
bool searchTrie(TrieNode *root, const char *word) {
    TrieNode *current = root;
    
    while (*word) {
        int index = *word - 'a';
        if (current->children[index] == NULL)
            return false;
        current = current->children[index];
        word++;
    }
    return current->isEndOfWord;
}

// Check if prefix exists (for autocomplete)
bool startsWith(TrieNode *root, const char *prefix) {
    TrieNode *current = root;
    
    while (*prefix) {
        int index = *prefix - 'a';
        if (current->children[index] == NULL)
            return false;
        current = current->children[index];
        prefix++;
    }
    return true;  // Prefix found
}

4. Huffman Coding (Data Compression)

// Huffman tree for lossless data compression
// More frequent characters get shorter codes

typedef struct HuffmanNode {
    char ch;           // Character (for leaves)
    int freq;          // Frequency
    struct HuffmanNode *left, *right;
} HuffmanNode;

// Build codes by traversing tree
void buildCodes(HuffmanNode *root, char *code, int depth) {
    if (root == NULL) return;
    
    // Leaf node - print character and its code
    if (root->left == NULL && root->right == NULL) {
        code[depth] = '\0';
        printf("'%c': %s\n", root->ch, code);
        return;
    }
    
    // Left edge = 0, Right edge = 1
    code[depth] = '0';
    buildCodes(root->left, code, depth + 1);
    
    code[depth] = '1';
    buildCodes(root->right, code, depth + 1);
}

// Example output for "aabbbc":
// 'b': 0      (most frequent - shortest code)
// 'a': 10
// 'c': 11

Common Tree Applications Summary