DSA Tutorial
🔍
Types of Trees
Overview: Tree Types at a Glance
TREE TYPES AND INTERVIEW IMPORTANCE: Binary Tree Foundation of all tree problems Binary Search Tree Left < Root < Right — search in O(log n) Heap Min/Max at root — priority queues Trie Prefix trees — string problems Segment Tree Range queries — competitive programming AVL Tree Self-balancing — know rotations conceptually Red-Black Tree Mostly conceptual — used in standard libraries
Each type adds a constraint or structure on top of the general tree from the previous page. Understanding what constraint each type adds — and why — is the key to knowing when to use which.
1. Binary Tree
What It Is
A Binary Tree is a tree where every node has at most two children — called the left child and the right child. No node can have three or more children. No restriction on values — any arrangement is valid.
1 ← root
/ \
2 3 ← level 1
/ \ \
4 5 6 ← level 2
/
7 ← level 3
Every node has AT MOST 2 children.
Node 1: left=2, right=3 ✓
Node 2: left=4, right=5 ✓
Node 3: no left, right=6 ✓ (having only one child is fine)
Node 5: left=7, no right ✓
Nodes 4, 6, 7: leaves ✓
Structural Variants
FULL BINARY TREE:
Every node has 0 or 2 children — never exactly 1.
1
/ \
2 3
/ \
4 5
Node 1: 2 children ✓ Node 2: 2 children ✓
Node 3: 0 children ✓ Nodes 4,5: 0 children ✓
──────────────────────────────────────────────────
COMPLETE BINARY TREE:
All levels fully filled except possibly the last,
which is filled from LEFT to RIGHT.
1
/ \
2 3
/ \ /
4 5 6 ← last level filled left to right ✓
Used as the backing structure for heaps.
──────────────────────────────────────────────────
PERFECT BINARY TREE:
All internal nodes have exactly 2 children AND
all leaf nodes are at the same level.
1
/ \
2 3
/ \ / \
4 5 6 7 ← all leaves at same level ✓
n levels → 2ⁿ - 1 nodes total.
──────────────────────────────────────────────────
DEGENERATE (SKEWED) TREE:
Every node has only one child — tree becomes a linked list.
1 1
\ /
2 2
\ /
3 3
\ /
4 4
Right-skewed Left-skewed
Height = n-1 (worst case for all tree algorithms)
Must-Learn Operations
TRAVERSALS (visit every node in a specific order):
PREORDER (Root → Left → Right): 1, 2, 4, 5, 7, 3, 6
INORDER (Left → Root → Right): 4, 2, 7, 5, 1, 3, 6
POSTORDER (Left → Right → Root): 4, 7, 5, 2, 6, 3, 1
LEVEL ORDER (BFS, level by level): 1, 2, 3, 4, 5, 6, 7 (with queue)
Using tree: 1
/ \
2 3
/ \ \
4 5 6
/
7
HEIGHT: longest root-to-leaf path = 3 (1→2→5→7)
DIAMETER: longest path between any two nodes (may not pass through root)
diameter = max(left_height + right_height) across all nodes
LCA: lowest common ancestor of two nodes = deepest node that is
ancestor of both. LCA(4,7) = 2, LCA(4,6) = 1
ZIGZAG TRAVERSAL: alternate left-to-right and right-to-left per level
Level 0 (L→R): 1
Level 1 (R→L): 3, 2
Level 2 (L→R): 4, 5, 6
Level 3 (R→L): 7
BOUNDARY TRAVERSAL: left boundary (top→down) + leaves + right boundary (bottom→up)
Why It Matters
Every tree problem builds on binary tree concepts. BST, Heap, AVL, Red-Black Trees are all specialised binary trees. Mastering traversals and recursive tree thinking here unlocks every other tree topic.
2. Binary Search Tree (BST)
What It Is
A Binary Search Tree is a binary tree with one additional rule on values:
BST PROPERTY:
For every node N:
All values in N's LEFT subtree < N's value
All values in N's RIGHT subtree > N's value
This holds RECURSIVELY for every node.
VALID BST:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
At node 8: left subtree {1,3,4,6,7} all < 8 ✓
right subtree {10,13,14} all > 8 ✓
At node 3: left {1} < 3, right {4,6,7} > 3 ✓
At node 10: no left, right {13,14} > 10 ✓
INVALID BST:
5
/ \
3 7
\
6 ← 6 > 5 but is in LEFT subtree of 5 ✗
Key Property: Inorder = Sorted
INORDER traversal of a BST always gives elements in SORTED (ascending) order.
BST: 8
/ \
3 10
/ \ \
1 6 14
Inorder: 1 → 3 → 6 → 8 → 10 → 14 ← sorted! ✓
This is why inorder traversal is used to:
- Validate a BST (check if inorder is sorted)
- Find kth smallest element (kth in inorder)
- Convert BST to sorted array
Must-Learn Operations
SEARCH O(log n) average:
Start at root. If target < node: go left. If target > node: go right.
Search 6 in the BST above:
8: 6 < 8 → go left
3: 6 > 3 → go right
6: 6 == 6 → FOUND ✓
INSERT O(log n) average:
Search for the insertion point (where search fails).
Insert as a new leaf at that position.
Insert 5: 8→left→3→right→6→left→4→right→5 inserted as right child of 4
DELETE — three cases:
Case 1: Node is a LEAF → simply remove it
Case 2: Node has ONE child → replace node with its child
Case 3: Node has TWO children → replace with INORDER SUCCESSOR
(smallest node in right subtree), then delete successor
FLOOR and CEIL:
Floor(x): largest value in BST ≤ x
Ceil(x): smallest value in BST ≥ x
Both O(log n) — follow BST property to narrow down
Complexity
Average Worst (skewed/degenerate) Search: O(log n) O(n) Insert: O(log n) O(n) Delete: O(log n) O(n) Worst case occurs when BST degenerates into a linked list (inserting sorted data: 1→2→3→4→5 creates a right-skewed tree). AVL and Red-Black trees fix this by keeping the tree balanced.
3. Heap
What It Is
A Heap is a complete binary tree satisfying the heap property: every parent node's value compares a specific way to its children.
MIN-HEAP: parent ≤ both children (minimum is always at root) MAX-HEAP: parent ≥ both children (maximum is always at root)
MIN-HEAP: MAX-HEAP:
1 9
/ \ / \
3 2 7 8
/ \ / \ / \ / \
6 5 4 8 2 4 5 1
Root = global minimum Root = global maximum
Every parent ≤ children Every parent ≥ children
Array Representation
Heaps are stored as arrays — the complete binary tree maps perfectly to indices:
MIN-HEAP array: [1, 3, 2, 6, 5, 4, 8]
0 1 2 3 4 5 6
Index arithmetic (0-based):
Parent of i: (i-1) / 2
Left child of i: 2*i + 1
Right child of i: 2*i + 2
Verification:
Node at index 1 (value 3):
Left child: 2×1+1 = 3 → arr[3] = 6 ✓
Right child: 2×1+2 = 4 → arr[4] = 5 ✓
Parent: (1-1)/2 = 0 → arr[0] = 1 ✓ (1 < 3 ✓)
Must-Learn Operations
INSERT (sift-up): add at end, bubble up until heap property restored
Insert 0 into min-heap [1, 3, 2, 6, 5, 4, 8]:
Add at end: [1, 3, 2, 6, 5, 4, 8, 0]
0 < parent(6) → swap: [1, 3, 2, 0, 5, 4, 8, 6]
0 < parent(3) → swap: [1, 0, 2, 3, 5, 4, 8, 6]
0 < parent(1) → swap: [0, 1, 2, 3, 5, 4, 8, 6]
O(log n)
EXTRACT-MIN (sift-down): remove root, put last element at root, bubble down
Remove 0 from [0, 1, 2, 3, 5, 4, 8, 6]:
Move last to root: [6, 1, 2, 3, 5, 4, 8]
6 > min child (1) → swap: [1, 6, 2, 3, 5, 4, 8]
6 > min child (3) → swap: [1, 3, 2, 6, 5, 4, 8]
O(log n)
HEAPIFY: build heap from unsorted array in O(n) — Floyd's algorithm
HEAP SORT: build max-heap, repeatedly extract max → O(n log n) in-place sort
Popular Interview Problems
kth largest element → min-heap of size k Top K frequent elements → min-heap of size k by frequency Merge K sorted arrays/lists → min-heap of (value, array_index) Median in data stream → max-heap (lower half) + min-heap (upper half)
4. Trie
What It Is
A Trie (prefix tree) is a tree where each edge represents a character. A path from the root to a node spells out a string prefix. It is used for fast prefix-based string operations.
Trie storing: ["cat", "car", "card", "care", "bat"]
(root)
/ \
c b
| |
a a
/ \ |
t r t
* | *
|
d e
* *
* marks end of a complete word
Path root→c→a→t = "cat" ✓
Path root→c→a→r = "car" ✓
Path root→c→a→r→d = "card" ✓
Path root→b→a→t = "bat" ✓
SHARED PREFIXES: "cat" and "car" share the path c→a (prefix "ca")
Stored ONCE, not duplicated. This is the key space advantage.
Node Structure
TRIE NODE: ┌────────────────────────────────────┐ │ children: array[26] (a-z) │ │ or HashMap<char, Node> │ │ isEndOfWord: boolean │ └────────────────────────────────────┘ children[0] = pointer to 'a' subtree (null if no 'a' child) children[1] = pointer to 'b' subtree ... children[25] = pointer to 'z' subtree isEndOfWord = true if a complete word ends at this node
Must-Learn Operations
INSERT "care": root → create/follow 'c' → 'a' → 'r' → create 'e' → mark isEndOfWord=true O(L) where L = length of word SEARCH "card": root → 'c' exists? yes → 'a' exists? yes → 'r' exists? yes → 'd' exists? yes → isEndOfWord at 'd'? yes → FOUND O(L) PREFIX SEARCH (startsWith "car"): Follow path c→a→r. If all characters exist: prefix present. Does NOT require isEndOfWord check. O(L) — all words with prefix "car" live in the subtree at 'r' AUTOCOMPLETE: prefix search + collect all words in the subtree
Popular Interview Problems
Autocomplete / type-ahead search → prefix search + subtree collection Word Dictionary (with '.' wildcard) → DFS through all children at '.' nodes Longest common prefix → follow path until branching point Word search in a grid → combine Trie with DFS on grid
COMPARISON: HashMap vs Trie for string storage
HashMap: O(L) insert/lookup (hashing)
cannot do prefix queries efficiently
O(n×L) space
Trie: O(L) insert/lookup (tree traversal)
O(L) prefix queries
shares prefixes → less space for many similar words
5. Segment Tree
What It Is
A Segment Tree is a binary tree built over an array. Each node stores an aggregate value (sum, min, max) for a contiguous range (segment) of the array. It enables both range queries and point updates in O(log n).
Array: [1, 3, 5, 7, 9, 11] (indices 0–5)
Segment Tree (range sum):
[0,5] = 36
/ \
[0,2] = 9 [3,5] = 27
/ \ / \
[0,1]=4 [2,2]=5 [3,4]=16 [5,5]=11
/ \ / \
[0,0]=1 [1,1]=3 [3,3]=7 [4,4]=9
Each node label: [range] = sum of arr[range]
Must-Learn Operations
BUILD: construct the tree bottom-up from array — O(n)
Leaf nodes = individual array elements
Internal nodes = aggregate of their children
RANGE QUERY (sum of arr[1..4]):
Query [1,4] on segment tree:
[0,5] does not fit in [1,4] → split
[0,2]: partially overlaps → split
[0,1]: partially overlaps → split
[0,0]: no overlap → skip
[1,1]: fully in [1,4] → return 3
[2,2]: fully in [1,4] → return 5
[3,5]: partially overlaps → split
[3,4]: fully in [1,4] → return 16
[5,5]: no overlap → skip
Total: 3 + 5 + 16 = 24 ✓ (arr[1]+arr[2]+arr[3]+arr[4] = 3+5+7+9 = 24)
O(log n)
POINT UPDATE (arr[2] += 4, so arr[2] becomes 9):
Update all nodes on path from root to leaf [2,2]:
[2,2] → [0,2] → [0,5]
Each updated in O(1) → total O(log n)
Comparison with Naive Array
Operation Naive array Segment Tree ───────────────────────────────────────────── Build O(1) O(n) Range query O(n) O(log n) Point update O(1) O(log n) Space O(n) O(4n) ≈ O(n) Use segment tree when: many range queries AND updates needed. Use prefix sums when: only range queries, no updates.
6. AVL Tree
What It Is
An AVL Tree is a self-balancing BST where the balance factor of every node is maintained at -1, 0, or +1.
BALANCE FACTOR of a node = height(left subtree) - height(right subtree) Allowed: -1, 0, +1 Violated: ±2 → triggers a ROTATION to restore balance
BALANCED AVL:
8 BF=0
/ \
4 10 BF(4)=0, BF(10)=0
/ \ \
2 6 14 BF(2)=0, BF(6)=0, BF(14)=0
All balance factors ∈ {-1,0,+1} ✓
UNBALANCED (BF=+2 at node 8 after inserting 2):
8 BF=+2 ← VIOLATION
/
4 BF=+1
/
2 BF=0
↑ inserted here — right rotation at 8 needed
The Four Rotations
LL ROTATION (imbalance in left-left direction): Right rotate at violation node
Unbalanced: C After right rotate at C: B
/ / \
B A C
/
A
RR ROTATION (imbalance in right-right direction): Left rotate at violation node
Unbalanced: A After left rotate at A: B
\ / \
B A C
\
C
LR ROTATION (left-right): Left rotate at child, then right rotate at violation
Unbalanced: C Left rotate at A: C Right rotate at C: B
/ / / \
A B A C
\ /
B A
RL ROTATION (right-left): Right rotate at child, then left rotate at violation
Mirror of LR rotation.
When to Use
AVL Tree vs BST: BST: O(log n) average, O(n) worst (skewed) AVL: O(log n) guaranteed always (strict balance) AVL Tree vs Red-Black Tree: AVL: stricter balance → faster lookups Red-Black: looser balance → fewer rotations on insert/delete → faster writes Use AVL when: read-heavy workload, lookup speed critical. Note: in interviews, AVL is usually tested conceptually (rotations, balance factor) — rarely implemented from scratch.
7. Red-Black Tree
What It Is
A Red-Black Tree is a self-balancing BST where every node is coloured red or black, and the tree maintains four colouring rules that together guarantee the tree stays approximately balanced.
RED-BLACK TREE RULES:
1. Every node is RED or BLACK.
2. The ROOT is always BLACK.
3. Every NULL leaf (sentinel) is BLACK.
4. If a node is RED, both its children are BLACK.
(No two consecutive red nodes on any path)
5. Every path from a node to any NULL leaf has the
same number of BLACK nodes. (Black-height property)
VALID Red-Black Tree (B=Black, R=Red):
10(B)
/ \
7(R) 15(B)
/ \ \
6(B) 9(B) 20(R)
Rule 1: all nodes coloured ✓
Rule 2: root 10 is Black ✓
Rule 4: Red nodes 7 and 20 have black children ✓
Rule 5: black-height = 2 on every root-to-null path ✓
(10→7→6→null: B, B, B = 3 blacks including null)
Why These Rules Work
Rule 4 (no two consecutive reds) + Rule 5 (equal black-height): The longest path in the tree (alternating R-B) is at most TWICE the length of the shortest path (all black). Shortest path: all black, length = black-height (bh) Longest path: alternating red-black = 2 × bh Therefore: height ≤ 2 × log₂(n+1) = O(log n) This guarantees O(log n) for all operations — without the strict AVL balance requirement.
Comparison with AVL
Property AVL Tree Red-Black Tree
──────────────────────────────────────────────────────
Balance Strict (BF ≤ 1) Loose (height ≤ 2×log n)
Lookup speed Faster Slightly slower
Insert/Delete More rotations Fewer rotations (amortized O(1))
Memory Height only Height + colour bit
Used in Read-heavy DBs General-purpose (Java TreeMap,
C++ std::map, Linux kernel)
INTERVIEW NOTE:
Red-Black Trees are almost never implemented in coding interviews.
Know: the colouring rules, why they ensure O(log n) height,
and how they compare to AVL trees.
Summary: All Tree Types at a Glance
TREE TYPE KEY CONSTRAINT INTERVIEW FOCUS
──────────────────────────────────────────────────────────────────
Binary Tree ≤ 2 children per node Traversals, height, LCA,
diameter, path sums
BST Left < Root < Right Search, insert, delete,
(recursive at every node) validate, kth smallest/largest
Heap Min/Max at root Priority queue operations,
(complete tree) (complete binary tree) kth largest, top-K, median
Trie Edges = characters Prefix search, autocomplete,
word dictionary
Segment Tree Each node = range aggregate Range queries, point updates,
competitive programming
AVL Tree Balance factor ∈ {-1,0,1} Rotations (LL,RR,LR,RL),
conceptual — rarely coded
Red-Black Tree Colouring rules maintain Colouring rules, comparison
O(log n) height with AVL — almost never coded
Choosing the Right Tree
PROBLEM TYPE USE ────────────────────────────────────────────────── Need O(log n) search by value? → BST / AVL / Red-Black Need to always access min or max? → Heap (Min or Max) Need prefix matching on strings? → Trie Need range queries on an array? → Segment Tree General tree traversal/structure? → Binary Tree Need guaranteed O(log n) BST? → AVL (reads) or Red-Black (writes)
In the next topics, you will explore each tree type in depth — starting with Binary Tree traversals and algorithms, then BST operations, and so on through each type above.
Suggested Quiz
In a Binary Search Tree, where are elements smaller than the root always stored?
1/6