DSA: Tree | Amr Tarek

Unlike arrays or linked lists (linear), a tree represents parent–child relationships, which makes it ideal for modeling structure, hierarchy, and fast searching.

Trees appear everywhere: file systems, compilers, databases, UI frameworks, and indexing engines.

At the top of the tree is the root, and every node can have zero or more children.

        Root
       /    \
     A        B
    / \        \
   C   D        E

Core Terminology

Node: a single element in the tree
Edge: connection between two nodes
Root: top-most node
Parent / Child: relationship between nodes
Leaf: node with no children
Depth: distance from root
Height: longest path to a leaf
Subtree: any node and its descendants

Tree Family

This is the full tree of tree-related structures you need for DSA

Tree
├── General Tree
│   └── N-ary Tree
│
├── Binary Tree
│   ├── Full Binary Tree
│   ├── Perfect Binary Tree
│   ├── Complete Binary Tree
│   └── Skewed Binary Tree
│
├── Binary Search Tree (BST)
│   ├── AVL Tree
│   ├── Red-Black Tree
│   └── Splay Tree
│
├── Heap
│   ├── Min Heap
│   └── Max Heap
│
├── Trie (Prefix Tree)
│
├── Segment Tree
│
└── B-Trees
    ├── B-Tree
    └── B+ Tree

General Tree

A General Tree allows each node to have any number of children.

All tree types conceptually start here.

struct Node {
    int value;
    vector<Node*> children;
};

Complexity

Traversal: O(n)
Space: O(n)

Use cases

File systems
Organization charts
DOM structure (HTML)

Binary Tree

A Binary Tree restricts each node to at most two children: left and right.

struct Node {
    int value;
    Node* left;
    Node* right;
};

Traversals

Inorder (Left → Root → Right)

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->value << " ";
    inorder(root->right);
}

Preorder (Root → Left → Right)

void preorder(Node* root) {
    if (!root) return;
    cout << root->value << " ";
    preorder(root->left);
    preorder(root->right);
}

Postorder (Left → Right → Root)

void postorder(Node* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->value << " ";
}

Complexity

Traversal: O(n)
Space (recursion): O(h)

Variants

Full Binary Tree

Every node has 0 or 2 children

      A
     / \
    B   C

Perfect Binary Tree

All levels completely filled

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

Complete Binary Tree

Filled left to right (used by heaps)

Skewed Tree

Degenerates into a linked list

A
 \
  B
   \
    C

Binary Search Tree (BST)

A BST maintains order:

Left subtree < root
Right subtree > root

Insert

Node* insert(Node* root, int value) {
    if (!root) return new Node{value, nullptr, nullptr};

    if (value < root->value)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);

    return root;
}

Search

bool search(Node* root, int key) {
    if (!root) return false;
    if (root->value == key) return true;

    if (key < root->value)
        return search(root->left, key);
    else
        return search(root->right, key);
}

Complexity

Average: O(log n)
Worst (skewed): O(n)

This is where balanced trees come in.

Complexity

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

Worst case happens when the tree becomes skewed.

_Why ordinary BSTs are not enough — and how balance saves performance_

A self-balancing tree is a binary search tree (BST) that automatically keeps its height small during insertions and deletions.

The goal is simple:

**Guarantee O(log n) time** for search, insert, and delete — _always_, not just on average.

Self-Balancing Trees

Used to guarantee logarithmic performance.

Every self-balancing tree:

Is a Binary Search Tree
Tracks structural information
Performs rotations when imbalance occurs

Balance is enforced locally, but guarantees global height bounds.

Tree Rotations (The Foundation)

Rotations are constant-time pointer rearrangements that restore balance without breaking BST order.

Right Rotation

Before:

After:

Left Rotation

Before:

After:

Key Rule

Rotations **preserve inorder traversal**, so BST ordering stays intact.

Rotation Cost

Time: O(1)
Space: O(1)

AVL Tree

Strict height balancing
Uses rotations

_Strictly balanced, mathematically clean_

An AVL Tree maintains this rule:

For every node,

**|height(left) − height(right)| ≤ 1**

This difference is called the balance factor.

Balance Factor

balanceFactor = height(left) - height(right)

Allowed values:

-1, 0, +1

Anything else → rebalance needed

AVL Rotations (4 Cases)

LL Case (Left-Left)

Right rotation on z

RR Case (Right-Right)

Left rotation on z

LR Case (Left-Right)

Left rotation on y

Right rotation on z

RL Case (Right-Left)

  z
   \
    y
   /
  x

Right rotation on y

Left rotation on z

AVL Insert (Core Logic)

Node* insert(Node* root, int key) {
    if (!root)
        return new Node(key);

    if (key < root->value)
        root->left = insert(root->left, key);
    else
        root->right = insert(root->right, key);

    updateHeight(root);

    int balance = getBalance(root);

    // LL
    if (balance > 1 && key < root->left->value)
        return rightRotate(root);

    // RR
    if (balance < -1 && key > root->right->value)
        return leftRotate(root);

    // LR
    if (balance > 1 && key > root->left->value) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    // RL
    if (balance < -1 && key < root->right->value) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

AVL Complexity

Operation	Time
Search	O(log n)
Insert	O(log n)
Delete	O(log n)

AVL Characteristics

Very strict balance
Smaller height
More rotations
Excellent for read-heavy workloads

Red-Black Tree

_Loosely balanced, industrial-grade_

A Red-Black Tree enforces balance using color rules instead of exact heights.

Looser balancing
Faster inserts/deletes
Used in std::map, std::set

Complexity

All operations:

O(log n) time
O(n) space

Red-Black Properties

Every node is red or black
Root is black
Red nodes cannot have red children
Every path from root to leaf has the same number of black nodes
Null leaves are considered black

These rules ensure:

Height ≤ **2 × log₂(n)**

Why Colors Work

Instead of tracking exact height:

Red nodes act as flexible connectors
Black nodes enforce global depth consistency

This reduces rotations.

Black-height consistency is preserved.

Rebalancing Strategy

Red-Black Trees use:

Recoloring (cheap)
Rotations (only when necessary)

Most fixes do not rotate.

Heap

A Heap is a complete binary tree with a special order.

Min Heap

Parent ≤ children

        1
      /   \
     3     5

Max Heap

Parent ≥ children

        9
      /   \
     7     4

Used for

Priority queues
Scheduling
Dijkstra’s algorithm

Array Representation

Index:  0  1  2  3  4
Value: [1, 3, 5, 7, 9]

Parent: (i - 1) / 2
Left: 2i + 1
Right: 2i + 2

Insert (Push)

priority_queue<int, vector<int>, greater<int>> minHeap;
minHeap.push(5);
minHeap.push(1);

Complexity

Operation	Time
Insert	O(log n)
Delete	O(log n)
Get Min/Max	O(1)

Trie (Prefix Tree)

A Trie stores strings character by character.

(root)
  |
  c
  |
  a
  |
  t*

struct TrieNode {
    bool isEnd = false;
    unordered_map<char, TrieNode*> children;
};

Used for

Autocomplete
Spell checking
Prefix search

Search complexity: O(length of word)

Insert

void insert(TrieNode* root, string word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->children[c])
            node->children[c] = new TrieNode();
        node = node->children[c];
    }
    node->isEnd = true;
}

Search

bool search(TrieNode* root, string word) {
    TrieNode* node = root;
    for (char c : word) {
        if (!node->children[c]) return false;
        node = node->children[c];
    }
    return node->isEnd;
}

Complexity

Insert/Search: O(k) where k = word length
Space: O(total characters)

Segment Tree

A Segment Tree is a binary tree used for range queries.

Example:

Range sum
Range minimum / maximum

        [0..7]
       /      \
   [0..3]   [4..7]

Query Complexity

Build: O(n)
Query: O(log n)
Update: O(log n)

Used heavily in competitive programming.

B-Trees Family

B-Tree

Multi-key nodes
Self-balanced
Disk-friendly

B+ Tree

All data stored in leaves
Fast range queries

Used in

Databases
File systems
Indexing engines

How Trees Connect to Hash Tables

Structure	Order	Search	Use
Hash Table	❌	O(1) avg	Fast lookup
BST	✅	O(log n)	Ordered data
Red-Black Tree	✅	O(log n)	Balanced maps
Trie	Prefix	O(k)	Strings

Hash Tables optimize speed
Trees optimize structure & ordering