Trees in Data Structures

Why Trees? (Advantages)

• Hierarchical Modeling: Naturally represents real-world hierarchies (File systems, DOM).
• Efficient Searching: Trees (like BST) offer $O(\log n)$ search time, significantly faster than $O(n)$ in arrays/linked lists.
• Dynamic Size: Like linked lists, trees grow and shrink dynamically without memory reallocation overhead.
• Fast Insertion/Deletion: Self-balancing trees guarantee $O(\log n)$ operations.

Real-World Applications

• Max Nodes at level L: $2^L$
• Max Nodes in tree of height H: $2^{H+1} - 1$
• Applications: Huffman coding, heaps, syntax trees.

class Node {
    int data;
    Node left, right;
    public Node(int item) {
        data = item;
        left = right = null;
    }
}

Interview Tip: Inorder traversal of a BST always returns a sorted array. Use this property to validate if a Binary Tree is a BST!

• Structure: Left (smaller), Mid (equal), Right (greater).
• Applications: Spell checking, Auto-complete, Dictionary matching.
• Advantage: Much more space-efficient than standard Tries for sparsely populated string sets.

class TSTNode {
    constructor(char) {
        this.data = char;
        this.isEndOfString = false;
        this.left = null;
        this.mid = null;
        this.right = null;
    }
}

Rotations (Rebalancing)

• LL (Left-Left): Right rotation.
• RR (Right-Right): Left rotation.
• LR (Left-Right): Left rotation on child, Right rotation on root.
• RL (Right-Left): Right rotation on child, Left rotation on root.

The 5 Sacred Properties

1. Every node is either Red or Black.
2. The Root is always Black.
3. Every Leaf (NIL) is Black.
4. If a node is Red, both its children are Black (No two consecutive Red nodes).
5. Every path from a node to its descendent leaves contains the same number of Black nodes (Black-Depth).

Use Case: Write-heavy apps. Used in Java's TreeMap, C++ std::map, and Linux Completely Fair Scheduler.

• Construction: Built bottom-up. Leaves represent array elements. Internal nodes represent merged results of children.
• Space: Requires $4N$ memory size array.
• Query: $O(\log N)$
• Update: $O(\log N)$

// Array representation is common
int tree[4 * MAX_N];
void build(int node, int start, int end) {
    if(start == end) { tree[node] = arr[start]; return; }
    int mid = (start + end) / 2;
    build(2*node, start, mid);
    build(2*node+1, mid+1, end);
    tree[node] = tree[2*node] + tree[2*node+1]; // Range Sum
}

Applications: File systems (folders can have many files/folders), Organizational charts, JSON/XML Document Object Model.

class NaryNode:
    def __init__(self, val):
        self.val = val
        self.children = [] # List of NaryNodes

B-Tree Properties

• All leaves are at the same level.
• A B-Tree of order $m$ can have at most $m-1$ keys and $m$ children per node.
• B+ Tree Diff: All data is stored only at the leaf nodes (linked together as a linked list for fast range queries), internal nodes only store keys for routing.