9. Trees

Tree Terminology

A tree is a hierarchical data structure composed of nodes connected by edges. Key definitions include:

Root: The topmost node with no parent.
Edge: A connection between a parent node and its child.
Leaf: A node that has zero children.
Internal node: A node with at least one child.
Depth of a node: Number of edges from the root to that node.
Height of a tree: Maximum depth among all nodes.
Subtree: The tree consisting of a node and all its descendants.
Degree: Number of children a node has.
Forest: A collection of disjoint trees.

Binary Tree

A binary tree restricts each node to at most two children, referred to as the left and right child.

Properties

Maximum nodes at level i (root level 0): 2^i.
Maximum nodes in a binary tree of height h: 2^{h+1} – 1.
Minimum possible height for a binary tree with n nodes: ⌊log₂(n+1)⌋ – 1.

Where:

i = level index (starting at 0)
h = height of the tree
n = total number of nodes

Traversals

In‑order (Left, Root, Right): Produces keys in sorted order for a Binary Search Tree (BST).
Pre‑order (Root, Left, Right): Useful for creating a copy of the tree.
Post‑order (Left, Right, Root): Employed during node deletion.
Level‑order (BFS): Visits nodes level by level from top to bottom.

Binary Search Tree (BST)

A BST maintains the invariant: for any node, all keys in its left subtree are less than the node’s key, and all keys in its right subtree are greater.

Operations

Search: O(h) where h is the tree height.
Insert: O(h).
Delete: O(h) (may require finding a successor or predecessor).

Example: inserting the sequence 50,30,70,20,40,60,80 yields a balanced BST.

Balanced Trees

Balanced trees enforce structural constraints to keep the height logarithmic, guaranteeing efficient operations.

AVL Tree

An AVL tree is a self‑balancing BST where the balance factor (height of left subtree minus height of right subtree) of every node is limited to ‑1, 0, or 1.

Rotations

Right Rotation (LL case): Applied when a left‑left imbalance occurs.
Left Rotation (RR case): Applied for a right‑right imbalance.
Left‑Right Rotation (LR case): Left rotation on the left child followed by a right rotation.
Right‑Left Rotation (RL case): Right rotation on the right child followed by a left rotation.

These rotations restore the AVL property in O(log n) time, ensuring search, insert, delete operations run in O(log n).

Example: Inserting 10,20,30 creates an LL imbalance at the root; a single right rotation restores balance.

Red‑Black Tree

A Red‑Black tree augments each node with a colour bit (red or black) and enforces:

The root is black.
Every leaf (NIL) is black.
Red nodes cannot have red children (no two consecutive reds).
Every path from a node to its descendant leaves contains the same number of black nodes.

These properties guarantee that the tree height is bounded by height ≤ 2·log₂(n+1), yielding O(log n) time for fundamental operations. Insertion and deletion involve recolouring and rotations (left/right) to maintain the invariants.

Red‑Black trees are widely used in implementations such as std::map (C++) and java.util.TreeMap (Java).

Advanced Trees

Heap

A heap is a complete binary tree that satisfies the heap property:

Min‑heap: parent.key ≤ children.keys.
Max‑heap: parent.key ≥ children.keys.

Because the tree is complete, it can be efficiently stored in an array. For a node at index i:

Left child: 2i + 1
Right child: 2i + 2
Parent: ⌊(i‑1)/2⌋

Operations

Insert: O(log n) (percolate up).
Extract‑min/max: O(log n) (remove root, replace with last element, percolate down).
Heapify: O(n) (build heap from an unordered array).

Heap sort builds a max‑heap then repeatedly extracts the maximum element to produce a sorted sequence.

Trie (Prefix Tree)

A trie stores strings by linking nodes that represent individual characters. The path from the root to a node spells a prefix; a terminal node marks the end of a word.

Use cases: Dictionary lookup, autocomplete, IP routing.
Complexity: Search and insertion run in O(L) where L is the length of the key.
Node structure: An array of size ALPHABET (or a hash map) plus a boolean end‑of‑word flag.

Segment Tree

A segment tree is a binary tree that aggregates information over intervals, enabling efficient range queries and point updates.

Stored values: Sum, minimum, maximum, GCD, etc.
Build: O(n).
Query: O(log n).
Update: O(log n).

Example: For the array [1,3,5,7,9,11], a segment tree can answer sum(2,5) (0‑based indexing) as 5 + 7 + 9 + 11 = 32.

Fenwick Tree (Binary Indexed Tree)

A Fenwick tree offers a simpler alternative to a segment tree for prefix‑sum queries.

Update: Add Δ to index i in O(log n).
Prefix sum query (1..i): Returns Σ_{k=1}^{i} a_k in O(log n).

Internal representation: tree[i] stores the sum of the range (i‑lowbit(i)+1 … i), where

lowbit(i) = i & (‑i)

Both operations run in logarithmic time, making the Fenwick tree ideal for cumulative frequency tables.

Applications

File System

Directories and files form a hierarchical tree. Each directory node contains references to its child files and subdirectories. Path resolution (e.g., /home/user/docs) is performed by traversing from the root following the path components.

HTML DOM

When a browser loads a web page, it parses the HTML into a Document Object Model (DOM) tree. Each element, attribute, and text node becomes a node in this tree. CSS selectors and JavaScript methods (e.g., querySelectorAll) navigate the DOM using tree traversal algorithms.

DNS

The Domain Name System organizes namespaces as a distributed tree. Each label (e.g., com, example, www) corresponds to a node. Resolving a domain like www.example.com involves traversing from the root through the com node, then example, finally www to retrieve the associated IP address.

Auto‑complete

A trie stores a dictionary of words. To suggest completions for a prefix P, the algorithm walks the trie following the characters of P (cost O(|P|)) and then enumerates all words in the resulting subtree. The total time is O(P + output size), making it ideal for real‑time suggestion boxes.