1. Binary Trees

A binary tree is a hierarchical data structure where each node has at most two children, commonly referred to as the left and right child.

Traversals

• Inorder (Left, Root, Right): Used in binary search trees to retrieve elements in sorted order.

void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    cout << root->data << " ";
    inorder(root->right);
}

• Preorder (Root, Left, Right): Useful for copying trees and expression evaluation.

void preorder(Node* root) {
    if (root == NULL) return;
    cout << root->data << " ";
    preorder(root->left);
    preorder(root->right);
}

• Postorder (Left, Right, Root): Used in tree deletion and expression tree evaluation.

void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->data << " ";
}

2. Binary Search Tree (BST)

A Binary Search Tree is a type of binary tree in which nodes follow the property: left child < parent < right child.

Operations

• Insertion: Insert elements maintaining the BST property.

Node* insert(Node* root, int val) {
    if (root == NULL) return new Node(val);
    if (val < root->data) root->left = insert(root->left, val);
    else root->right = insert(root->right, val);
    return root;
}

• Deletion: Remove elements while keeping the BST structure intact.

Node* deleteNode(Node* root, int val) {
    if (root == NULL) return root;
    if (val < root->data) root->left = deleteNode(root->left, val);
    else if (val > root->data) root->right = deleteNode(root->right, val);
    else {
        if (root->left == NULL) return root->right;
        else if (root->right == NULL) return root->left;
        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

3. AVL Trees and Red-Black Trees

Self-balancing binary search trees maintain balance to optimize operations.

AVL Trees

AVL trees maintain balance using rotations and ensure O(log N) operations.

int getHeight(Node* root) {
    return (root == NULL) ? 0 : root->height;
}

Red-Black Trees

A self-balancing BST with an additional color property ensuring log-time operations.

4. Trie (Prefix Tree)

A tree structure for storing strings efficiently.

Applications

• Autocomplete
• Dictionary Search

struct TrieNode {
    TrieNode* children[26];
    bool isEndOfWord;
    TrieNode() {
        isEndOfWord = false;
        for (int i = 0; i < 26; i++)
            children[i] = NULL;
    }
};

5. Segment Trees and Fenwick Trees

Used for efficient range queries.

Segment Tree

Divides an array into segments for quick query processing.

void buildSegmentTree(int arr[], int segTree[], int left, int right, int pos) {
    if (left == right) {
        segTree[pos] = arr[left];
        return;
    }
    int mid = (left + right) / 2;
    buildSegmentTree(arr, segTree, left, mid, 2*pos + 1);
    buildSegmentTree(arr, segTree, mid+1, right, 2*pos + 2);
    segTree[pos] = segTree[2*pos + 1] + segTree[2*pos + 2];
}

Fenwick Tree

A binary indexed tree (BIT) used for prefix sum calculations.

void updateBIT(int BITree[], int n, int index, int val) {
    index += 1;
    while (index <= n) {
        BITree[index] += val;
        index += index & (-index);
    }
}