Note: Inorder predecessor (maximum in left subtree) can also be used instead of inorder successor.
Hierarchical data structures - Binary Trees, BST, AVL, B-Trees
Data Structure Module - Learn hierarchical data organization
Think of a family tree or file folder structure:
[ROOT]
/ \
[A] [B]
/ \ \
[C] [D] [E]
Terminology:
- ROOT: Top node (no parent)
- LEAF: Bottom nodes (no children) - C, D, E
- PARENT: A is parent of C, D
- CHILD: C, D are children of A
- HEIGHT: Longest path from root to leaf = 2
A Binary Tree is a hierarchical (non-linear) data structure where each node has at most 2 children — Left Child and Right Child.
Key Shift: All previous structures (Array, Stack, Queue, Linked List) were linear (one path). Binary Tree is non-linear — branching paths! This is a fundamental upgrade in structural thinking.
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None # Left child
self.right = None # Right child
# Creating a tree manually
# 1
# / \
# 2 3
# / \
# 4 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
Every node has either 0 or 2 children. No node has just 1 child.
Full Binary Tree: NOT Full:
[1] [1]
/ \ / \
[2] [3] [2] [3]
/ \ /
[4] [5] [4]
Every internal node Node 2 has only
has exactly 2 children 1 child → NOT full
All levels are completely filled except possibly the last level, and the last level is filled from left to right.
Complete: NOT Complete:
[1] [1]
/ \ / \
[2] [3] [2] [3]
/ \ \
[4] [5] [5]
Last level fills Last level has gap
from LEFT to RIGHT on the left → NOT complete
A complete binary tree does NOT have to be a full binary tree.
All internal nodes have exactly 2 children AND all leaf nodes are at the same level.
Perfect Binary Tree:
[1] Level 0: 1 node
/ \
[2] [3] Level 1: 2 nodes
/ \ / \
[4] [5][6] [7] Level 2: 4 nodes
Every level is completely filled!
A Perfect Binary Tree is BOTH Full AND Complete.
| Formula | Description |
|---|---|
| Min nodes = h + 1 | Minimum nodes in a binary tree of height h |
| Max nodes = 2^(h+1) − 1 | Maximum nodes in a binary tree of height h |
| Max nodes at level L = 2^L | Maximum nodes at any given level |
| Leaf nodes = n₂ + 1 | Leaf nodes = (nodes with degree 2) + 1 |
| Height of complete tree = ⌊log₂n⌋ | Height grows logarithmically |
Example: Height h = 3
Min nodes = 3 + 1 = 4 (one node per level)
Max nodes = 2^(3+1) − 1 = 15 (perfect binary tree)
Level 0: max 2^0 = 1 node
Level 1: max 2^1 = 2 nodes
Level 2: max 2^2 = 4 nodes
Level 3: max 2^3 = 8 nodes
The number of structurally different binary trees that can be formed with n nodes:
Formula: (2n C n) / (n + 1)
This is called the CATALAN NUMBER.
Example 1: n = 3
= (6 C 3) / (3 + 1)
= 20 / 4
= 5 distinct binary trees
Example 2: n = 6
= (12 C 6) / (6 + 1)
= 924 / 7
= 132 distinct binary trees
The 5 distinct binary trees for n = 3:
[R] [R] [R] [R] [R]
/ / \ / \ \
/ / \ / \ \
/ [A] [A] [A] [B] [A]
| \ / /
[A] [B] [B] [B]
\
[B]
| Property | Formula |
|---|---|
| Leaf nodes (L) | L = Internal nodes (I) + 1 |
| Total nodes | 2^(h+1) − 1 |
| Internal nodes | 2^h − 1 |
| Leaf nodes | 2^h |
Height convention: Height = number of edges in longest path from root to leaf. Root alone has height 0.
There are 4 ways to visit every node. Memorize these!
def inorder(root):
if root:
inorder(root.left) # 1. Go left
print(root.val, end=" ") # 2. Visit node
inorder(root.right) # 3. Go right
# For tree: 1
# / \
# 2 3
# / \
# 4 5
# Output: 4 2 5 1 3
def preorder(root):
if root:
print(root.val, end=" ") # 1. Visit node FIRST
preorder(root.left) # 2. Go left
preorder(root.right) # 3. Go right
# Output: 1 2 4 5 3
def postorder(root):
if root:
postorder(root.left) # 1. Go left
postorder(root.right) # 2. Go right
print(root.val, end=" ") # 3. Visit node LAST
# Output: 4 5 2 3 1
from collections import deque
def level_order(root):
if not root:
return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val, end=" ")
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Output: 1 2 3 4 5 (level by level!)
A Binary Search Tree is a node-based binary tree with the following properties:
The Golden Rule: Left < Root < Right
This ordering allows efficient searching, insertion, and deletion.
50
/ \
30 70
/ \ / \
20 40 60 80
- All values left of 50 are < 50
- All values right of 50 are > 50
- This makes searching FAST!
| Operation | Average Case | Worst Case (Skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
All operations depend on height h of the tree → O(h). Balanced = O(log n), Skewed = O(n).
Algorithm Steps:
Key insight: New keys are always inserted at a leaf position while maintaining BST property.
class BST:
def __init__(self):
self.root = None
def insert(self, val):
self.root = self._insert(self.root, val)
def _insert(self, node, val):
# Base case: empty spot found! Insert here.
if not node:
return TreeNode(val)
# Decide: go left or right?
if val < node.val:
node.left = self._insert(node.left, val)
elif val > node.val:
node.right = self._insert(node.right, val)
return node
def search(self, val):
return self._search(self.root, val)
def _search(self, node, val):
if not node:
return False # Not found
if node.val == val:
return True # Found!
if val < node.val:
return self._search(node.left, val)
else:
return self._search(node.right, val)
# Usage
bst = BST()
for num in [50, 30, 70, 20, 40, 60, 80]:
bst.insert(num)
print(bst.search(40)) # True
print(bst.search(45)) # False
Deletion is the trickiest BST operation. There are 3 cases:
Simply remove the node. No children to worry about.
Delete 20:
30 30
/ \ / \
20 40 → [X] 40
Node 20 is a leaf → just remove it!
Replace the node with its child.
Delete 20 (has one child 10):
30 30
/ \ / \
20 40 → 10 40
/
10
Node 20 replaced by its only child 10.
Delete 30 (has two children):
30 35
/ \ / \
20 40 → 20 40
/ \ / \
35 50 37 50
\
37
Step 1: Inorder successor of 30 = 35 (min in right subtree)
Step 2: Copy 35 into node 30's position
Step 3: Delete original 35 (Case 2: has one child 37)
Note: Inorder predecessor (maximum in left subtree) can also be used instead of inorder successor.
The inorder successor of a node is the node with the smallest value greater than the given node. It is found by going to the right subtree and then going left as far as possible.
def find_min(node):
"""Find minimum value node (leftmost node)"""
current = node
while current.left:
current = current.left
return current
# Inorder successor of node X = find_min(X.right)
def delete(self, val):
self.root = self._delete(self.root, val)
def _delete(self, node, val):
if not node:
return node
# Step 1: Find the node
if val < node.val:
node.left = self._delete(node.left, val)
elif val > node.val:
node.right = self._delete(node.right, val)
else:
# Found the node to delete!
# Case 1 & 2: No child or one child
if not node.left:
return node.right
elif not node.right:
return node.left
# Case 3: Two children
# Find inorder successor (min in right subtree)
successor = find_min(node.right)
node.val = successor.val
# Delete the inorder successor
node.right = self._delete(node.right, successor.val)
return node
Insert: 30, 20, 10, 15, 25, 23, 39, 35, 42
Step-by-step:
Insert 30 → root
Insert 20 → left of 30
Insert 10 → left of 20
Insert 15 → right of 10
Insert 25 → right of 20
Insert 23 → left of 25
Insert 39 → right of 30
Insert 35 → left of 39
Insert 42 → right of 39
Final BST:
30
/ \
20 39
/ \ / \
10 25 35 42
\ /
15 23
IMPORTANT FACT: Inorder traversal of this BST gives sorted order: 10, 15, 20, 23, 25, 30, 35, 39, 42
Each comparison eliminates half the remaining nodes!
BUT if you insert sorted data (1,2,3,4,5), it becomes a "linked list" and O(n)!
Balanced BST: Skewed BST (sorted insert):
30 1
/ \ \
20 40 2
/ \ \
10 25 3
\
Height = 2 4
Search = O(log n) \
5
Height = 4
Search = O(n) ← disaster!
Next intellectual jump: AVL Trees (self-balancing BST) solve this skewing problem. That's where trees stop misbehaving!
AVL Tree = Self-Balanced BST (named after inventors Adelson-Velsky and Landis)
BST adds order. AVL adds discipline. BST says "keep values sorted." AVL says "also keep the tree short." Short trees = fast searches.
A binary tree is an AVL tree if:
Balance Factor = Height of Left Subtree − Height of Right Subtree
Allowed values: -1, 0, +1
+1 → Left heavy (left subtree is taller)
0 → Perfectly balanced
-1 → Right heavy (right subtree is taller)
If any node has BF outside {-1, 0, +1} → TREE IS UNBALANCED!
AVL Tree (balanced): NOT AVL (unbalanced):
[30] BF=0 [30] BF=+2 ← violation!
/ \ /
[20] [40] [20] BF=+1
BF=0 BF=0 /
[10] BF=0
All BFs are -1, 0, +1 Node 30 has BF = 2 → needs rotation!
When imbalance occurs, rotations are performed at the nearest ancestor whose balance factor becomes ±2. There are 4 types:
When: New node inserted in left subtree of left child. Fix: Single Right Rotation (clockwise).
Before (LL case): After (Right Rotation):
[30] BF=+2 [20] BF=0
/ / \
[20] BF=+1 [10] [30]
/ BF=0 BF=0
[10] BF=0
Node 20 becomes the new root of this subtree.
When: New node inserted in right subtree of right child. Fix: Single Left Rotation (anticlockwise).
Before (RR case): After (Left Rotation):
[10] BF=-2 [20] BF=0
\ / \
[20] BF=-1 [10] [30]
\ BF=0 BF=0
[30] BF=0
Node 20 becomes the new root of this subtree.
When: New node inserted in right subtree of left child. Fix: Two rotations:
Before (LR case): After Step 1: After Step 2:
[30] BF=+2 [30] BF=+2 [20] BF=0
/ / / \
[10] BF=-1 [20] BF=+1 [10] [30]
\ / BF=0 BF=0
[20] BF=0 [10] BF=0
Step 1: Left rotate at 10 Step 2: Right rotate at 30
When: New node inserted in left subtree of right child. Fix: Two rotations:
Before (RL case): After Step 1: After Step 2:
[10] BF=-2 [10] BF=-2 [20] BF=0
\ \ / \
[30] BF=+1 [20] BF=-1 [10] [30]
/ \ BF=0 BF=0
[20] BF=0 [30] BF=0
Step 1: Right rotate at 30 Step 2: Left rotate at 10
How to detect which rotation is needed:
1. Find the first unbalanced ancestor (BF = ±2)
2. Check the PATH from that ancestor to the new node:
Path goes Left → Left = LL → Single Right Rotation
Path goes Right → Right = RR → Single Left Rotation
Path goes Left → Right = LR → Left then Right Rotation
Path goes Right → Left = RL → Right then Left Rotation
Steps:
1. Insert node as in normal BST (at leaf position)
2. Walk back up to root, updating heights of ancestors
3. Compute balance factor at each ancestor
4. If any node has BF = ±2 → perform the appropriate rotation
5. Done! Tree is balanced again.
| Operation | BST (worst) | AVL (always) |
|---|---|---|
| Search | O(n) | O(log n) |
| Insert | O(n) | O(log n) |
| Delete | O(n) | O(log n) |
The guarantee: BST can degrade to O(n) with skewed input. AVL guarantees O(log n) for ALL operations. That guarantee is the entire reason AVL exists.
Next upgrade: Red-Black Trees — same self-balancing idea, different balancing philosophy (less strict, fewer rotations).
B-Trees are extended Binary Search Trees specialized in m-way searching. Instead of 2 children (binary), each node can have up to m children and store multiple keys.
The deeper insight: AVL optimized height in RAM. B-Tree optimizes height for disk. When datasets are huge and RAM is small compared to disk, B-Trees become kings.
For a B-Tree of order m:
Maximum keys per node = m − 1
Minimum keys per node = ⌈m/2⌉ − 1
Maximum children = m
Minimum children = ⌈m/2⌉
Example: Order m = 4
┌──────────────────┬───────┐
│ Property │ Value │
├──────────────────┼───────┤
│ Max keys │ 3 │
│ Min keys │ 1 │
│ Max children │ 4 │
│ Min children │ 2 │
└──────────────────┴───────┘
B-Tree of order 3 (2-3 Tree):
[20 | 40] ← root has 2 keys, 3 children
/ | \
[10] [25|30] [50|60] ← leaves at same level
Each internal node: 1 to 2 keys, 2 to 3 children
All leaves at level 1
Keys sorted within each node
Problem: Disk access is SLOW compared to RAM
Binary tree (height ~20 for 1M nodes) = 20 disk reads
B-Tree (order 100, same 1M nodes) = ~3 disk reads!
Fewer levels = fewer disk accesses = MUCH faster!
| Operation | Time Complexity |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
B+ Trees are extensions of B-Trees designed for even more efficient sequential access.
B-Tree: B+ Tree:
┌────────┐ ┌────────┐
│ 20|40 │ ← has data │ 20|40 │ ← keys ONLY (no data)
├────────┤ ├────────┤
│ 10|30 │ ← has data │ 10|30 │ ← keys ONLY
└────────┘ └────────┘
↓
┌────────────────────┐
│ Leaf nodes have ALL │
│ data + linked list │
└────────────────────┘
B-Tree: Data in internal + leaf nodes
B+ Tree: Data ONLY in leaf nodes
Leaves connected as LINKED LIST
When main memory is limited:
• Internal nodes → stored in main memory (small, keys only)
• Leaf nodes → stored in secondary storage (large, has data)
Benefits:
1. Internal nodes are SMALLER (no data) → more keys fit in RAM
2. Linked leaves → efficient RANGE QUERIES (scan left to right)
3. All searches end at leaf level → uniform access time
| Feature | B-Tree | B+ Tree |
|---|---|---|
| Data storage | Internal + Leaf nodes | Leaf nodes only |
| Leaf linking | No | Yes (linked list) |
| Range queries | Slower | Faster |
| Search path | May end at any level | Always ends at leaf |
| Internal node size | Larger (has data) | Smaller (keys only) |
| Used in | File systems | Databases (MySQL, PostgreSQL) |
| Operation | Time Complexity |
|---|---|
| Search | O(log n) |
| Insert | O(log n) |
| Delete | O(log n) |
The evolution: BST → AVL (balanced in RAM) → B-Tree (balanced for disk) → B+ Tree (optimized sequential disk access + databases)
| Operation | BST Average | BST Worst | AVL |
|---|---|---|---|
| Search | O(log n) | O(n) | O(log n) |
| Insert | O(log n) | O(n) | O(log n) |
| Delete | O(log n) | O(n) | O(log n) |
Traversal Mnemonics:
One-liner for each concept:
| Concept | Key Takeaway |
|---|---|
| Tree | Hierarchical data structure; root at top, leaves at bottom. |
| Traversal | Inorder (sorted output for BST), Preorder (copying), Postorder (deleting). |
| BST | binary search tree; left < root < right. O(log n) search if balanced. |
| AVL / Red-Black | Self-balancing trees; guarantee O(log n) operations. |
| B-Trees | Fat nodes (multiple keys/children); optimized for disk access (databases). |
| Trie | Prefix tree; extremely fast for string matching/auto-complete. |
Essential Code Snippets:
# Typical Tree Node
class TreeNode:
def __init__(self, val=0):
self.val = val
self.left = None
self.right = None
# DFS: Inorder Traversal
def inorder(root):
if not root: return []
return inorder(root.left) + [root.val] + inorder(root.right)
# BFS: Level Order Traversal (using Queue)
from collections import deque
def bfs(root):
if not root: return
queue = deque([root])
while queue:
node = queue.popleft()
print(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
The Golden Rules:
Video Courses:
Articles & Visualizations:
Practice Problems:
Test your understanding with step-by-step solutions
40 questions · 90s per question
Each question has a 90-second time limit. Unanswered questions will be auto-submitted when time runs out.