Binary Tree in C - Traversals, BST, AVL

Tree Terminologies

🌳 Basic Terms

Term	Definition
Root	Topmost node of the tree
Parent	Node that has child nodes
Child	Node directly connected to another node when moving away from root
Sibling	Nodes with same parent
Leaf	Node with no children
Internal Node	Node with at least one child
Depth	Number of edges from root to node
Height	Number of edges on longest path from node to leaf
Level	Root at level 0, children at level 1, etc.
Degree	Number of children of a node

        1          ← Root (Level 0, Depth 0)
       / \
      2   3        ← Level 1
     / \   \
    4   5   6      ← Level 2 (Leaves)
   
    Node 1: Parent of 2,3 | Degree 2 | Height 2
    Node 2: Parent of 4,5 | Child of 1 | Degree 2
    Node 4: Leaf | Child of 2 | Depth 2

Binary Tree Properties

📐 Key Mathematical Properties

Maximum nodes at level i: 2^i
Maximum nodes in tree of height h: 2^(h+1) - 1
Minimum nodes in tree of height h: h + 1
For any non-empty binary tree: n0 = n2 + 1
(n0 = leaf nodes, n2 = nodes with 2 children)
Height of tree with n nodes: ⌊log₂(n)⌋ to n-1

Binary Tree Representations

1. Array Representation

For complete binary tree: Left child at 2i+1, Right child at 2i+2

Tree:        1
            / \
           2   3
          / \   \
         4   5   6

Array Index: 0  1  2  3  4  5
Array:     [1, 2, 3, 4, 5, 6]

Node at index i:
  - Left child: 2*i + 1
  - Right child: 2*i + 2
  - Parent: (i-1) / 2

array_representation.c

#include <stdio.h>
#include <math.h>
#define MAX 100

void insert(int tree[], int* size, int data) {
    if (*size >= MAX) {
        printf("Tree is full!\n");
        return;
    }
    tree[*size] = data;
    (*size)++;
}

int leftChild(int tree[], int index, int size) {
    int left = 2 * index + 1;
    return (left < size) ? tree[left] : -1;
}

int rightChild(int tree[], int index, int size) {
    int right = 2 * index + 2;
    return (right < size) ? tree[right] : -1;
}

void display(int tree[], int size) {
    printf("Array representation: ");
    for (int i = 0; i < size; i++)
        printf("%d ", tree[i]);
    printf("\n");
}

int main() {
    int tree[MAX], size = 0;
    
    insert(tree, &size, 1);
    insert(tree, &size, 2);
    insert(tree, &size, 3);
    insert(tree, &size, 4);
    insert(tree, &size, 5);
    
    display(tree, size);
    
    printf("Left child of %d: %d\n", tree[0], leftChild(tree, 0, size));
    printf("Right child of %d: %d\n", tree[0], rightChild(tree, 0, size));
    
    return 0;
}

2. Linked Representation

linked_representation.c

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

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

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

int main() {
    // Create tree:     1
    //                /   \
    //               2     3
    //              / \   /
    //             4   5 6
    
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    
    printf("Root: %d\n", root->data);
    printf("Left child: %d\n", root->left->data);
    printf("Right child: %d\n", root->right->data);
    
    return 0;
}

Binary Tree Traversals

🔄 Types of Traversals

Traversal	Order	Use Case
Inorder	Left-Root-Right	Gives sorted order for BST
Preorder	Root-Left-Right	Copy/serialize tree
Postorder	Left-Right-Root	Delete tree, expression evaluation

        1
       / \
      2   3
     / \   \
    4   5   6

Inorder:   4 → 2 → 5 → 1 → 3 → 6    (Left-Root-Right)
Preorder:  1 → 2 → 4 → 5 → 3 → 6    (Root-Left-Right)
Postorder: 4 → 5 → 2 → 6 → 3 → 1    (Left-Right-Root)

traversals.c

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

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

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

// Preorder: Root -> Left -> Right
void preorder(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// Inorder: Left -> Root -> Right
void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// Postorder: Left -> Right -> Root
void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

int main() {
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->right = createNode(6);
    
    printf("Preorder:   "); preorder(root); printf("\n");
    printf("Inorder:    "); inorder(root); printf("\n");
    printf("Postorder:  "); postorder(root); printf("\n");
    
    return 0;
}

Complexity

Traversal	Time	Space
Inorder/Preorder/Postorder	O(n)	O(h) recursion stack

Threaded Binary Trees

🔗 Concept

Threaded binary trees store pointers to inorder predecessor/successor in null child pointers to optimize traversal without recursion or stack.

Single Threaded: Store one thread (successor or predecessor)
Double Threaded: Store both predecessor and successor

Advantages:

Inorder traversal without stack (O(1) space)
Faster successor/predecessor access
Efficient for frequent traversal operations

Binary Search Tree (BST)

A BST is a binary tree where: Left subtree values < Root < Right subtree values

bst_complete.c

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

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

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

// Insert into BST
Node* insert(Node* root, int data) {
    if (root == NULL) return createNode(data);
    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);
    return root;
}

// Search in BST
Node* search(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);
}

// Find minimum
Node* findMin(Node* root) {
    while (root->left != NULL) root = root->left;
    return root;
}

// Find maximum
Node* findMax(Node* root) {
    while (root->right != NULL) root = root->right;
    return root;
}

// Delete from BST
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;
    
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        // Node with one or no child
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        // Node with two children
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

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

int main() {
    Node* root = NULL;
    int values[] = {50, 30, 70, 20, 40, 60, 80};
    int n = sizeof(values)/sizeof(values[0]);
    
    for (int i = 0; i < n; i++)
        root = insert(root, values[i]);
    
    printf("Inorder (sorted): "); inorder(root); printf("\n");
    
    if (search(root, 40)) printf("Found 40\n");
    
    printf("Min: %d, Max: %d\n", findMin(root)->data, findMax(root)->data);
    
    root = deleteNode(root, 30);
    printf("After deleting 30: "); inorder(root); printf("\n");
    
    return 0;
}

Operation	Average	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

AVL Trees (Self-Balancing BST)

⚖️ Balance Factor

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

Valid values: -1, 0, 1 (tree is balanced)

🔁 Rotations

Rotation	Condition	Action
LL (Left Rotation)	BF > 1, left heavy	Right rotate
RR (Right Rotation)	BF < -1, right heavy	Left rotate
LR (Left-Right)	BF > 1, right-heavy left	Left rotate, then right rotate
RL (Right-Left)	BF < -1, left-heavy right	Right rotate, then left rotate

Time Complexity: All operations O(log n) guaranteed

Expression Trees

Binary tree representation of arithmetic expressions.

Infix: (A + B) * (C - D)
Postfix: A B + C D - *

Expression Tree:
        *
       / \
      +   -
     / \  / \
    A  B C  D

Inorder: A + B * C - D (need parentheses)
Preorder: * + A B - C D (Polish notation)
Postorder: A B + C D - * (Reverse Polish notation)

Tree Applications

📁 File Systems

Directory structures, folder hierarchies

🔍 Expression Evaluation

Compilers use expression trees

🗂️ Decision Trees

Machine learning, game trees

📊 Database Indexing

B-trees, B+ trees for efficient retrieval

🗜️ Compression

Huffman coding trees

🌐 Routing Tables

Network routing, DNS

Summary Table

Topic	Key Concept	Time Complexity
Tree Traversals	Inorder, Preorder, Postorder	O(n)
BST Search	Left < Root < Right	O(log n) avg, O(n) worst
BST Insert/Delete	Recursive insertion/deletion	O(log n) avg, O(n) worst
AVL Tree	Self-balancing, \|BF\| ≤ 1	O(log n) guaranteed
Threaded Tree	Inorder without stack	O(1) space traversal