Loading...
Loading...
Phase 1: Technical Theory | Date: 30 July 2026 | Subject: Trees, Graphs, Sorting and Searching | Questions in Exam: Part of Approximately 8 DSA Questions
Today we will study important non-linear data structures and algorithms.
| Hour | Topic | Main Target |
|---|---|---|
| 1 | Binary Trees | Understand terminology, types and mathematical properties |
| 2 | Tree Traversals and BST | Perform inorder, preorder and postorder; insert, search and delete in a BST |
| 3 | Graphs and Hashing | Understand graph representations, BFS, DFS and collision handling |
| 4 | Sorting | Learn Bubble, Selection, Insertion, Quick, Merge and Heap Sort |
| 5 | Searching and Big-O | Compare Linear and Binary Search; understand time and space complexity |
After completing this material, you will be able to:
A tree is a non-linear data structure made of nodes connected by edges.
Unlike an array or linked list, a tree does not form one simple sequence. It forms a hierarchy.
Examples of hierarchical structures:
A
/ \
B C
/ \ \
D E F
In this tree:
Use this tree for the definitions:
A
/ \
B C
/ \ / \
D E F G
/
H
A node is an individual element of a tree.
Nodes in the example:
A, B, C, D, E, F, G, H
An edge is a connection between two nodes.
Examples:
AβB
AβC
BβD
BβE
A tree with n nodes has exactly:
n β 1 edges
The example has 8 nodes, so it has:
8 β 1 = 7 edges
The root is the topmost node.
In the example:
Root = A
A tree has one root.
A node directly above another node is its parent.
Examples:
A node directly below another node is its child.
Examples:
Nodes with the same parent are siblings.
Examples:
A leaf node, also called an external or terminal node, has no children.
Leaf nodes in the example:
D, F, G, H
An internal node, also called a non-leaf node, has at least one child.
Internal nodes:
A, B, C, E
The degree of a node is its number of children.
| Node | Children | Degree |
|---|---|---|
| A | B, C | 2 |
| B | D, E | 2 |
| C | F, G | 2 |
| E | H | 1 |
| D | None | 0 |
The degree of a tree is the maximum degree of any node.
In the example:
Degree of tree = 2
A path is a sequence of connected nodes.
Example:
A β B β E β H
The path contains:
An ancestor is a node above another node on a path toward the root.
Ancestors of H:
E, B, A
A descendant is a node below another node.
Descendants of B:
D, E, H
A subtree is a node together with all its descendants.
Subtree rooted at B:
B
/ \
D E
/
H
A forest is a collection of separate trees.
If the root of a tree is removed, its subtrees form a forest.
Different books sometimes number levels differently. In this document:
The depth of a node is the number of edges from the root to that node.
For the example:
| Node | Depth |
|---|---|
| A | 0 |
| B, C | 1 |
| D, E, F, G | 2 |
| H | 3 |
In this document:
Level = Depth
Therefore, root level is 0.
Some exam books use root level 1. Always check the convention used in the question.
The height of a node is the number of edges on the longest downward path from that node to a leaf.
Examples:
The height of a tree is the height of its root.
For the example:
Height = 3 edges
If levels are counted from 0:
Number of levels = Height + 1
Therefore:
Number of levels = 4
Some books count height using nodes instead of edges.
Under that convention:
In exam numericals, first identify the convention.
A binary tree is a tree in which each node has at most two children.
The two children are distinguished as:
Example:
10
/ \
20 30
/ \ \
40 50 60
A node may have:
It cannot have more than two children.
A full binary tree is a binary tree in which every node has either:
No node has exactly one child.
A
/ \
B C
/ \
D E
This is full because:
A
/ \
B C
/
D
B has exactly one child, so this tree is not full.
A full binary tree may also be called:
Terminology may vary between books, so focus on the definition.
If:
I = number of internal nodesL = number of leavesThen:
L = I + 1
Total nodes:
N = 2I + 1
Therefore, a full binary tree always has an odd number of total nodes.
Example:
Internal nodes = 3
Leaves = 3 + 1 = 4
Total nodes = 3 + 4 = 7
A complete binary tree satisfies these conditions:
A
/ \
B C
/ \ /
D E F
The final level is filled from left to right.
A
/ \
B C
\ /
E F
B has a right child without a left child. There is a gap before a filled position, so the tree is not complete.
A complete binary tree can be stored efficiently in an array because it has no internal gaps.
If 1-based indexing is used:
| Relationship | Formula |
|---|---|
Left child of node at index i | 2i |
Right child of node at index i | 2i + 1 |
Parent of node at index i | floor(i/2) |
If 0-based indexing is used:
| Relationship | Formula |
|---|---|
| Left child | 2i + 1 |
| Right child | 2i + 2 |
| Parent | floor((i β 1)/2) |
A binary heap is normally a complete binary tree.
A perfect binary tree satisfies both conditions:
Example:
A
/ \
B C
/ \ / \
D E F G
This tree is:
If root is at level 0 and height is h:
Maximum nodes at level l:
2^l
Total nodes:
2^(h + 1) β 1
Number of leaves:
2^h
Number of internal nodes:
2^h β 1
Example for height 3:
Total nodes
= 2^(3 + 1) β 1
= 2^4 β 1
= 16 β 1
= 15
Leaves:
2^3 = 8
Internal nodes:
2^3 β 1 = 7
Check:
7 internal + 8 leaves = 15 total nodes
A balanced binary tree is a tree whose height does not become excessively large compared with its number of nodes.
In a height-balanced tree, the left and right subtree heights at a node usually differ by only a small allowed amount.
For an AVL tree, the difference is at most 1.
20
/ \
10 30
/ \ /
5 15 25
10
\
20
\
30
\
40
Balanced trees usually provide faster searching because their height remains near log n.
A skewed tree is a tree in which most or all nodes have only one child.
40
/
30
/
20
/
10
10
\
20
\
30
\
40
A skewed tree behaves much like a linked list.
For n nodes, its height using the edge convention is:
n β 1
| Type | Main Rule |
|---|---|
| Binary tree | At most two children per node |
| Full binary tree | Every node has 0 or 2 children |
| Complete binary tree | All levels full except possibly last; last filled left to right |
| Perfect binary tree | Every internal node has 2 children and all leaves are at same level |
| Balanced binary tree | Height remains reasonably small |
| Skewed binary tree | Nodes mostly have only one child |
FCP
Assume:
lMaximum nodes = 2^l
Example:
| Level | Maximum Nodes |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
hMaximum nodes = 2^(h + 1) β 1
hMaximum leaves = 2^h
hA skewed tree gives the minimum:
Minimum nodes = h + 1
Example:
Height = 4
Minimum nodes = 5
n NodesUsing edge-based height:
Minimum height = ceil(logβ(n + 1)) β 1
A commonly used equivalent for complete-tree reasoning is:
Height = floor(logβ n)
for a complete binary tree with n nodes.
For any non-empty tree with n nodes:
Edges = n β 1
In a linked binary tree with n nodes:
Number of NULL child links = n + 1
Reason:
2n pointer fields.n β 1 real edges.2n β (n β 1) = n + 1.Traversal means visiting every node of a tree in a systematic order.
The main traversals are:
The first three are depth-first traversals.
Use:
N = Node or rootL = Left subtreeR = Right subtree| Traversal | Order | Memory Rule |
|---|---|---|
| Preorder | NLR | Node first |
| Inorder | LNR | Node in the middle |
| Postorder | LRN | Node last |
PREorder = Root PREcedes children
INorder = Root is IN between
POSTorder = Root comes POST, or after, children
Order:
Node β Left β Right
Algorithm:
Visit root
Traverse left subtree in preorder
Traverse right subtree in preorder
Use this tree:
A
/ \
B C
/ \ / \
D E F G
Preorder:
A B D E C F G
Step-by-step:
Order:
Left β Node β Right
Algorithm:
Traverse left subtree in inorder
Visit root
Traverse right subtree in inorder
For the same tree:
A
/ \
B C
/ \ / \
D E F G
Inorder:
D B E A F C G
Inorder traversal of a Binary Search Tree gives keys in sorted ascending order, assuming ordinary ordering and no unusual duplicate rule.
Order:
Left β Right β Node
Algorithm:
Traverse left subtree in postorder
Traverse right subtree in postorder
Visit root
For the same tree:
D E B F G C A
The root is processed after both subtrees.
Level-order visits nodes one level at a time from left to right.
For the example tree:
A B C D E F G
Level-order uses a queue.
Basic method:
Level-order traversal is closely related to Breadth-First Search.
| Traversal | Order | Common Application |
|---|---|---|
| Preorder | NLR | Copy tree, prefix expression |
| Inorder | LNR | Sorted BST output, infix expression |
| Postorder | LRN | Delete tree, postfix expression |
| Level-order | Level by level | Breadth-wise processing |
Tree:
1
/ \
2 3
/ \ \
4 5 6
Root 1
Left subtree: 2, 4, 5
Right subtree: 3, 6
Answer:
1 2 4 5 3 6
Left subtree: 4, 2, 5
Root: 1
Right subtree: 3, 6
Answer:
4 2 5 1 3 6
Left subtree: 4, 5, 2
Right subtree: 6, 3
Root: 1
Answer:
4 5 2 6 3 1
1 2 3 4 5 6
Tree:
10
/ \
5 20
\ / \
8 15 30
/
12
10 5 8 20 15 12 30
5 8 10 12 15 20 30
8 5 12 15 30 20 10
10 5 20 8 15 30 12
A Binary Search Tree, or BST, is a binary tree that follows an ordering rule.
For each node:
Example:
50
/ \
30 70
/ \ / \
20 40 60 80
This is a BST.
A binary tree and a Binary Search Tree are not the same.
A binary tree only limits each node to two children.
A BST additionally maintains key order.
BST duplicate handling depends on the implementation.
Possible rules:
An exam question should normally specify the rule. If it does not, assume distinct keys.
Search for 60:
50
/ \
30 70
/ \
60 80
Steps:
Search follows only one path.
At each node:
| Tree Shape | Search Time |
|---|---|
| Balanced BST | O(log n) |
| Average ordinary BST | O(log n), under typical assumptions |
| Skewed BST | O(n) |
A skewed BST behaves like a linked list.
To insert a key:
Insert:
50, 30, 70, 20, 40, 60, 80
50 becomes root.
30 < 50, so place it to the left.
70 > 50, so place it to the right.
20 < 50
20 < 30
Place left of 30.
40 < 50
40 > 30
Place right of 30.
60 > 50
60 < 70
Place left of 70.
80 > 50
80 > 70
Place right of 70.
Final BST:
50
/ \
30 70
/ \ / \
20 40 60 80
Inorder:
20 30 40 50 60 70 80
Insert:
10, 20, 30, 40, 50
Result:
10
\
20
\
30
\
40
\
50
This is a skewed BST.
Now insert:
30, 20, 40, 10, 25, 35, 50
Result:
30
/ \
20 40
/ \ / \
10 25 35 50
The same values can produce different BST shapes when inserted in different orders.
The minimum key is found by repeatedly moving left.
Minimum = leftmost node
The maximum key is found by repeatedly moving right.
Maximum = rightmost node
For:
50
/ \
30 70
/ \
20 80
Minimum = 20
Maximum = 80
The inorder predecessor of a node is the value immediately before it in inorder traversal.
If a node has a left subtree, its predecessor is usually:
Maximum node in the left subtree
The inorder successor is the value immediately after a node in inorder traversal.
If a node has a right subtree, its successor is usually:
Minimum node in the right subtree
Example BST:
50
/ \
30 70
/ \ / \
20 40 60 80
Inorder:
20 30 40 50 60 70 80
For 50:
Predecessor = 40
Successor = 60
BST deletion has three cases.
A leaf has no children.
Before deleting 20:
50
/ \
30 70
/ \
20 40
Remove 20 directly:
50
/ \
30 70
\
40
Before deleting 30:
50
/ \
30 70
\
40
Node 30 has one child, 40.
Connect 50 directly to 40:
50
/ \
40 70
Before deleting 50:
50
/ \
30 70
/ \ / \
20 40 60 80
A node with two children can be replaced by either:
Using inorder successor:
Successor of 50 = 60
Replace 50 with 60, then delete the original 60:
60
/ \
30 70
/ \ \
20 40 80
Z-O-T
Let h be the tree height.
| Operation | Time |
|---|---|
| Search | O(h) |
| Insert | O(h) |
| Delete | O(h) |
| Minimum | O(h) |
| Maximum | O(h) |
| Traversal | O(n) |
For a balanced BST:
h β logβ n
Therefore:
Search, insert, delete = O(log n)
For a skewed BST:
h = n β 1
Therefore:
Search, insert, delete = O(n)
8
/ \
4 12
/ \ / \
2 6 10 14
Answers:
Preorder: 8 4 2 6 12 10 14
Inorder: 2 4 6 8 10 12 14
Postorder: 2 6 4 10 14 12 8
Level-order: 8 4 12 2 6 10 14
A
/ \
B C
\ \
D E
/
F
Answers:
Preorder: A B D C E F
Inorder: B D A C F E
Postorder: D B F E C A
Level-order: A B C D E F
25
/ \
15 40
/ \ /
10 20 30
/ \
28 35
Answers:
Preorder: 25 15 10 20 40 30 28 35
Inorder: 10 15 20 25 28 30 35 40
Postorder: 10 20 15 28 35 30 40 25
Level-order: 25 15 40 10 20 30 28 35
A graph is a non-linear data structure consisting of:
A graph is commonly written as:
G = (V, E)
Where:
V = set of verticesE = set of edgesExample:
V = {A, B, C, D}
E = {
AβB,
AβC,
BβD,
CβD
}
Diagram:
A
/ \
B C
\ /
D
Graphs represent relationships such as:
Use:
A ----- B
| |
| |
C ----- D
A point in the graph.
Vertices:
A, B, C, D
A connection between two vertices.
Edges:
AβB, AβC, BβD, CβD
Two vertices are adjacent if an edge connects them.
Examples:
In an undirected graph, the degree of a vertex is the number of edges touching it.
For the diagram:
Degree(A) = 2
Degree(B) = 2
Degree(C) = 2
Degree(D) = 2
For an undirected graph:
Sum of all vertex degrees = 2 Γ Number of edges
Therefore:
Ξ£ degree(v) = 2E
In the example:
Sum of degrees = 2 + 2 + 2 + 2 = 8
Edges = 4
2E = 8
A path is a sequence of connected vertices.
Example:
A β B β D
Path length is the number of edges in the path.
For:
A β B β D
Path length:
2
A cycle is a path that starts and ends at the same vertex without repeating edges unnecessarily.
Example:
A β B β D β C β A
An undirected graph is connected if every vertex can be reached from every other vertex.
A graph is disconnected if some vertices cannot reach others.
Edges have no direction.
A ----- B
This means A is connected to B and B is connected to A.
Examples:
Edges have direction.
A -----> B
This means there is an edge from A to B. It does not automatically mean an edge from B to A.
Examples:
A directed graph is also called a digraph.
For a directed graph:
Example:
A -----> B
C -----> B
B -----> D
For B:
In-degree(B) = 2
Out-degree(B) = 1
For any directed graph:
Sum of all in-degrees = Number of edges
Sum of all out-degrees = Number of edges
Edges have no numerical cost.
A ----- B
Each edge has a value such as distance, cost or time.
A ---5--- B
Examples:
An edge from a vertex to itself.
A ----> A
More than one edge connecting the same pair of vertices.
A graph allowing parallel edges is often called a multigraph.
An adjacency matrix uses a two-dimensional matrix.
For an unweighted graph:
1 means an edge exists.0 means no edge exists.Graph:
A ----- B
| |
C ----- D
Vertex order:
A, B, C, D
Adjacency matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 0 | 1 |
| C | 1 | 0 | 0 | 1 |
| D | 0 | 1 | 1 | 0 |
For an undirected graph, the matrix is symmetric around the main diagonal.
That is:
Matrix[i][j] = Matrix[j][i]
For a directed graph, it may not be symmetric.
For V vertices:
O(VΒ²)
Checking whether a particular edge exists takes:
O(1)
An adjacency matrix is useful for a dense graph, where many possible edges exist.
An adjacency list stores a list of neighbours for every vertex.
For the same graph:
A: B, C
B: A, D
C: A, D
D: B, C
For an undirected or directed graph:
O(V + E)
For an undirected graph, each edge normally appears in two neighbour lists.
Searching for a particular neighbour may take time proportional to the degree of the vertex.
An adjacency list is usually better for a sparse graph, where relatively few edges exist.
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Structure | V Γ V matrix | List of neighbours |
| Space | O(VΒ²) | O(V + E) |
| Test a specific edge | O(1) | O(degree), typically |
| Visit all neighbours | O(V) | O(degree) |
| Best for | Dense graphs | Sparse graphs |
| Easy implementation | Yes | Also common |
| Undirected storage | Matrix symmetric | Each edge listed twice |
Dense β Matrix
Sparse β List
BFS stands for Breadth-First Search.
It visits vertices level by level.
BFS first visits:
BFS uses a queue.
BFS = Broad first
BFS = Queue
Basic steps:
Marking a vertex when it is enqueued prevents duplicate entries.
Graph:
A
/ \
B C
/ \ \
D E---F
Assume neighbours are processed alphabetically.
Adjacency list:
A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E
Start at A.
| Step | Removed | Newly Added | Queue | Output |
|---|---|---|---|---|
| 1 | A | B, C | B, C | A |
| 2 | B | D, E | C, D, E | A, B |
| 3 | C | F | D, E, F | A, B, C |
| 4 | D | None | E, F | A, B, C, D |
| 5 | E | None; F already discovered | F | A, B, C, D, E |
| 6 | F | None | Empty | A, B, C, D, E, F |
BFS order:
A B C D E F
Traversal order may change if neighbour order changes. The algorithm remains BFS as long as vertices are processed level by level.
In an unweighted graph, BFS finds a path with the minimum number of edges from the starting vertex.
With an adjacency list:
Time = O(V + E)
Every vertex and edge is processed a limited number of times.
Space:
O(V)
With an adjacency matrix:
Time = O(VΒ²)
because a complete row of the matrix may be checked for every vertex.
DFS stands for Depth-First Search.
It explores one path as deeply as possible before returning, or backtracking.
DFS uses:
DFS = Deep first
DFS = Stack
Recursive idea:
Iterative DFS uses an explicit stack.
Use the graph:
A
/ \
B C
/ \ \
D E---F
Assume alphabetical neighbour order and recursive DFS.
Start at A:
DFS order:
A B D E F C
A different valid order may occur with a different neighbour order.
With an adjacency list:
Time = O(V + E)
Space:
O(V)
With an adjacency matrix:
Time = O(VΒ²)
| Feature | BFS | DFS |
|---|---|---|
| Full Form | Breadth-First Search | Depth-First Search |
| Main structure | Queue | Stack or recursion |
| Strategy | Level by level | Deep path first |
| Unweighted shortest path | Yes | Not guaranteed |
| Memory use | Can be high for wide graphs | Can be high for deep graphs |
| Tree equivalent | Level-order | Preorder-like exploration |
| Applications | Minimum-edge paths | Cycle detection, backtracking |
| Adjacency-list time | O(V + E) | O(V + E) |
Hashing is a technique used to store and retrieve data quickly using a computed table index.
A hash function converts a key into an array index.
Example:
Hash table size = 10
Hash function h(k) = k mod 10
For key 47:
h(47) = 47 mod 10 = 7
Store 47 at index 7.
| Index | Value |
|---|---|
| 0 | β |
| 1 | β |
| 2 | β |
| 3 | β |
| 4 | β |
| 5 | β |
| 6 | β |
| 7 | 47 |
| 8 | β |
| 9 | β |
A good hash function should be:
A collision occurs when two different keys produce the same hash index.
Example:
h(k) = k mod 10
h(27) = 7
h(47) = 7
Both keys want index 7.
Collisions are normal. A hash table needs a method to handle them.
The main methods are:
In separate chaining, each table position stores a linked list or another collection of keys.
Example:
Index 7 -> 27 -> 47 -> 57 -> NULL
Table:
| Index | Chain |
|---|---|
| 0 | β |
| 1 | 21 |
| 2 | β |
| 3 | 33 β 43 |
| 4 | β |
| 5 | 15 |
| 6 | β |
| 7 | 27 β 47 β 57 |
| 8 | β |
| 9 | β |
In open addressing, all elements are stored inside the hash-table array.
If the calculated slot is occupied, another slot is searched using a probe sequence.
Main methods:
Linear probing checks the next positions one by one.
Formula:
hα΅’(k) = [h(k) + i] mod m
Where:
m = table sizei = 0, 1, 2, 3, ...Example:
Table size = 10
h(k) = k mod 10
Insert 27:
h(27) = 7
Store at 7.
Insert 47:
h(47) = 7, occupied
Check 8
Store at 8.
Insert 57:
h(57) = 7, occupied
Check 8, occupied
Check 9
Store at 9.
Linear probing may form long groups of occupied consecutive slots. This is called primary clustering.
Quadratic probing uses squared increments.
A common form is:
hα΅’(k) = [h(k) + iΒ²] mod m
Probe additions:
0Β², 1Β², 2Β², 3Β², ...
That is:
0, 1, 4, 9, ...
It reduces primary clustering but may still have other clustering or coverage issues depending on table size and formula.
Double hashing uses a second hash function to determine the step size.
A common form:
hα΅’(k) = [hβ(k) + i Γ hβ(k)] mod m
It generally distributes probes better than linear probing.
The second hash value should not be zero and should work well with the table size.
| Feature | Chaining | Open Addressing |
|---|---|---|
| Collision storage | External list or collection | Inside table |
| Table may exceed number of slots | Yes | No |
| Pointer memory | Usually required | Not required |
| Deletion | Relatively easy | Requires care |
| Cache locality | Lower | Often better |
| Performance depends on | Chain length | Probe length |
The load factor tells how full a hash table is.
Symbol:
Ξ±, pronounced alpha
Formula:
Ξ± = n / m
Where:
n = number of stored keysm = number of table slotsExample:
7 keys in 10 slots
Ξ± = 7/10 = 0.7
For open addressing:
Ξ± must remain below 1
As load factor increases, collisions and probe lengths usually increase.
| Case | Search/Insert/Delete |
|---|---|
| Average, good distribution | O(1) |
| Worst case | O(n) |
Worst case may occur when many keys collide.
Sorting means arranging data in an order.
Examples:
Sorting is important because it can:
A sorting algorithm is stable if equal-key elements keep their original relative order.
Example records:
(Asha, 80)
(Ravi, 70)
(Neha, 80)
After stable sorting by marks:
(Ravi, 70)
(Asha, 80)
(Neha, 80)
Asha remains before Neha because both have 80.
An in-place algorithm uses only a small amount of extra memory.
Typical extra space:
O(1)
Some algorithms use recursion stack space even when their array rearrangement is in-place.
An adaptive sort performs better when the input is already or nearly sorted.
Insertion Sort is adaptive.
An optimized Bubble Sort can also be adaptive.
A comparison sort determines order by comparing elements.
All six required algorithms are comparison sorts.
Bubble Sort repeatedly compares adjacent elements.
If two adjacent elements are in the wrong order, it swaps them.
After each full pass, the largest unsorted element βbubblesβ to the end.
Sort:
5, 1, 4, 2
Compare 5 and 1:
1, 5, 4, 2
Compare 5 and 4:
1, 4, 5, 2
Compare 5 and 2:
1, 4, 2, 5
The largest value 5 reaches its final position.
Compare 1 and 4:
1, 4, 2, 5
Compare 4 and 2:
1, 2, 4, 5
Compare 1 and 2:
1, 2, 4, 5
Sorted.
For n elements, Bubble Sort needs at most:
n β 1 passes
Use a swap flag.
If a complete pass makes no swaps, the array is already sorted and the algorithm stops.
| Case | Time |
|---|---|
| Best, with swap flag | O(n) |
| Average | O(nΒ²) |
| Worst | O(nΒ²) |
| Extra space | O(1) |
Selection Sort repeatedly selects the smallest element from the unsorted part and places it at the beginning.
Sort:
64, 25, 12, 22, 11
Smallest in full list = 11
Swap 64 and 11:
11, 25, 12, 22, 64
Unsorted portion:
25, 12, 22, 64
Smallest = 12
11, 12, 25, 22, 64
Unsorted portion:
25, 22, 64
Smallest = 22
11, 12, 22, 25, 64
11, 12, 22, 25, 64
Sorted.
Selection Sort performs roughly the same number of comparisons even if the input is already sorted.
Comparisons:
n(n β 1)/2
| Case | Time |
|---|---|
| Best | O(nΒ²) |
| Average | O(nΒ²) |
| Worst | O(nΒ²) |
| Extra space | O(1) |
Selection Sort can be useful when writing or swapping data is expensive because it uses relatively few swaps.
Insertion Sort builds a sorted portion one element at a time.
It takes the next element and inserts it into the correct position among the already sorted elements.
Real-life analogy:
Arranging playing cards in your hand
Sort:
5, 2, 4, 6, 1, 3
Initially, 5 is treated as sorted.
2, 5, 4, 6, 1, 3
Shift 5 right and place 4:
2, 4, 5, 6, 1, 3
6 is already correctly placed:
2, 4, 5, 6, 1, 3
Shift 6, 5, 4 and 2:
1, 2, 4, 5, 6, 3
Shift 6, 5 and 4:
1, 2, 3, 4, 5, 6
Sorted.
| Case | Time |
|---|---|
| Best, already sorted | O(n) |
| Average | O(nΒ²) |
| Worst, reverse sorted | O(nΒ²) |
| Extra space | O(1) |
Quick Sort uses the divide-and-conquer method.
Main steps:
A pivot is the value used to divide the array.
Sort:
6, 3, 8, 5, 2, 7, 4, 1
Choose pivot:
4
Conceptual partition:
Smaller than 4: 3, 2, 1
Pivot: 4
Larger than 4: 6, 8, 5, 7
Result after conceptual partition:
3, 2, 1, 4, 6, 8, 5, 7
Then recursively sort:
3, 2, 1
and:
6, 8, 5, 7
Final result:
1, 2, 3, 4, 5, 6, 7, 8
Actual array states depend on the partition method.
The pivot divides the data into nearly equal parts.
n/2 and n/2
Time:
O(n log n)
Partitions are reasonably balanced.
Time:
O(n log n)
The pivot repeatedly produces:
0 elements on one side
n β 1 elements on the other side
This may happen when:
Time:
O(nΒ²)
Random pivot selection or median-based techniques reduce the chance of repeated bad partitions.
Typical recursion space:
Merge Sort also uses divide and conquer.
Steps:
Sort:
38, 27, 43, 3, 9, 82, 10
[38, 27, 43, 3] [9, 82, 10]
Further divide:
[38, 27] [43, 3] [9, 82] [10]
Further divide:
[38] [27] [43] [3] [9] [82] [10]
[38] + [27] -> [27, 38]
[43] + [3] -> [3, 43]
[9] + [82] -> [9, 82]
Next:
[27, 38] + [3, 43]
-> [3, 27, 38, 43]
[9, 82] + [10]
-> [9, 10, 82]
Final:
[3, 27, 38, 43] + [9, 10, 82]
-> [3, 9, 10, 27, 38, 43, 82]
| Case | Time |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n log n) |
| Extra array space | O(n) |
It requires additional memory for merging in common array implementations.
A binary heap is a complete binary tree satisfying a heap-order rule.
Every parent is greater than or equal to its children.
Example:
50
/ \
30 40
/ \ /
10 20 35
The root contains the largest value.
Every parent is less than or equal to its children.
The root contains the smallest value.
A heap is not the same as a BST.
In a max heap:
To sort in ascending order:
Array:
4, 10, 3, 5, 1
Build max heap:
10, 5, 3, 4, 1
Swap root with last:
1, 5, 3, 4, 10
Restore heap in first four elements:
5, 4, 3, 1, 10
Swap root with last active element:
1, 4, 3, 5, 10
Restore:
4, 1, 3, 5, 10
Continue until sorted:
1, 3, 4, 5, 10
Heapify restores the heap property in a tree or subtree.
| Case | Time |
|---|---|
| Best | O(n log n) |
| Average | O(n log n) |
| Worst | O(n log n) |
| Extra space | O(1) for array rearrangement |
Building the initial heap can be done in:
O(n)
The complete Heap Sort remains:
O(n log n)
| Algorithm | Best Time | Average Time | Worst Time | Extra Space | Stable? | In-Place? |
|---|---|---|---|---|---|---|
| Bubble, optimized | O(n) | O(nΒ²) | O(nΒ²) | O(1) | Yes | Yes |
| Selection | O(nΒ²) | O(nΒ²) | O(nΒ²) | O(1) | No | Yes |
| Insertion | O(n) | O(nΒ²) | O(nΒ²) | O(1) | Yes | Yes |
| Quick | O(n log n) | O(n log n) | O(nΒ²) | O(log n) average recursion | No | Usually yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) for arrays | Yes | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
Among todayβs six algorithms:
BIM
These are normally stable.
BIS
Average and worst cases are O(nΒ²).
MH
Quick Sort is O(n log n) on average but O(nΒ²) in the worst case.
Think:
Insertion Sort
Optimized Bubble Sort also improves, but Insertion Sort is the standard strong choice among simple sorts.
| Situation | Suitable Choice |
|---|---|
| Small, nearly sorted data | Insertion Sort |
| Need stability and guaranteed O(n log n) | Merge Sort |
| Need fast average array sorting | Quick Sort |
| Need O(n log n) worst case and low extra array space | Heap Sort |
| Need very few swaps | Selection Sort |
| Educational adjacent-swap algorithm | Bubble Sort |
| External sorting, data does not fully fit in RAM | Merge Sort |
Searching means finding whether a required value exists in a collection and, if it exists, locating its position.
The required value is called:
The two main methods today are:
Linear Search checks elements one by one from the beginning until:
Example:
Array = [12, 7, 25, 9, 30]
Target = 9
Comparisons:
Compare with 12 β Not found
Compare with 7 β Not found
Compare with 25 β Not found
Compare with 9 β Found
Target found at index 3 using 0-based indexing.
| Case | Situation | Time |
|---|---|---|
| Best | Target is first element | O(1) |
| Average | Target is somewhere in middle | O(n) |
| Worst | Target is last or absent | O(n) |
| Extra space | Iterative implementation | O(1) |
For n elements:
Maximum comparisons = n
Binary Search requires the data to be sorted.
This is the most important condition.
Binary Search repeatedly compares the target with the middle element.
At each step:
Each comparison removes approximately half of the remaining elements.
Sorted array:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Value | 10 | 20 | 30 | 40 | 50 | 60 | 70 |
Search for 60.
Initial values:
low = 0
high = 6
Middle:
mid = floor((0 + 6) / 2)
= 3
At index 3:
Value = 40
Since:
60 > 40
Search right half:
low = 4
high = 6
New middle:
mid = floor((4 + 6) / 2)
= 5
At index 5:
Value = 60
Found.
Number of comparisons:
2
A basic formula is:
mid = (low + high) / 2
A safer formula that avoids possible integer overflow is:
mid = low + (high β low) / 2
Use integer division or floor when needed.
Array:
10, 20, 30, 40, 50, 60, 70
Search for 35.
Search stops when:
low > high
Suppose there are 16 elements.
After each comparison:
16 β 8 β 4 β 2 β 1
Number of divisions:
4
Because:
2^4 = 16
logβ16 = 4
For 1024 elements:
logβ1024 = 10
Only about 10 halving steps are needed.
Therefore:
Binary Search time = O(log n)
| Case | Time |
|---|---|
| Best | O(1) |
| Average | O(log n) |
| Worst | O(log n) |
| Iterative extra space | O(1) |
| Recursive extra space | O(log n) due to call stack |
For a successful or unsuccessful search, a common bound is close to:
floor(logβ n) + 1
Exact counts depend on implementation and whether the target is found early.
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data must be sorted | No | Yes |
| Strategy | Check one by one | Repeatedly halve range |
| Best time | O(1) | O(1) |
| Average time | O(n) | O(log n) |
| Worst time | O(n) | O(log n) |
| Suitable structure | Array or linked list | Random-access sorted array |
| Simple for small data | Yes | Requires sorted data |
| Efficient for large sorted array | No | Yes |
Binary Search is not normally efficient on a linked list because reaching the middle node is not O(1).
Algorithm complexity describes how an algorithmβs resource use grows as input size grows.
Main resources:
How the number of operations grows.
How much extra memory grows with input size.
Big-O notation describes an asymptotic upper bound on growth.
In beginner exam questions, it is commonly used to describe worst-case or general growth rate.
It ignores:
Example:
T(n) = 3nΒ² + 5n + 10
For large n, nΒ² dominates.
Therefore:
T(n) = O(nΒ²)
From fastest growth to slowest performance:
| Complexity | Name | Example |
|---|---|---|
| O(1) | Constant | Array index access |
| O(log n) | Logarithmic | Binary Search |
| O(n) | Linear | Linear Search |
| O(n log n) | Linearithmic | Merge Sort |
| O(nΒ²) | Quadratic | Selection Sort |
| O(nΒ³) | Cubic | Some triple nested loops |
| O(2^n) | Exponential | Some subset problems |
| O(n!) | Factorial | Trying every permutation |
O(1)
<
O(log n)
<
O(n)
<
O(n log n)
<
O(nΒ²)
<
O(nΒ³)
<
O(2^n)
<
O(n!)
Smaller growth is normally better for large input.
Access one array element.
Complexity:
O(1)
Repeat from 1 to n.
Complexity:
O(n)
First loop runs n times.
Second loop runs n times.
Total:
n + n = 2n
Ignore constant 2:
O(n)
Outer loop runs n times.
Inner loop runs n times for each outer iteration.
Total:
n Γ n = nΒ²
Complexity:
O(nΒ²)
n
n/2
n/4
n/8
...
Complexity:
O(log n)
Many divide-and-conquer algorithms perform:
O(n) work per level
O(log n) levels
Total:
O(n log n)
Merge Sort follows this pattern.
O(2n) = O(n)
O(n + 100) = O(n)
O(nΒ² + n) = O(nΒ²)
O(5nΒ³ + 2nΒ² + 7) = O(nΒ³)
Keep the fastest-growing term and drop constant multipliers.
Minimum work for an input of size n.
Example:
Linear Search finds the target first:
O(1)
Expected work over typical inputs.
Example:
Linear Search:
O(n)
Maximum work for an input of size n.
Example:
Linear Search target is absent:
O(n)
Worst-case analysis is common because it gives an upper guarantee.
| Operation or Algorithm | Typical Complexity |
|---|---|
| Array indexed access | O(1) |
| Tree traversal | O(n) |
| Balanced BST search | O(log n) |
| Skewed BST search | O(n) |
| BFS with adjacency list | O(V + E) |
| DFS with adjacency list | O(V + E) |
| Hash table average search | O(1) |
| Hash table worst search | O(n) |
| Linear Search | O(n) |
| Binary Search | O(log n) |
| Bubble Sort average | O(nΒ²) |
| Selection Sort | O(nΒ²) |
| Insertion Sort average | O(nΒ²) |
| Quick Sort average | O(n log n) |
| Merge Sort | O(n log n) |
| Heap Sort | O(n log n) |
Tree:
40
/ \
20 60
/ \ / \
10 30 50 70
Find all traversals.
Preorder:
40 20 10 30 60 50 70
Inorder:
10 20 30 40 50 60 70
Postorder:
10 30 20 50 70 60 40
Level-order:
40 20 60 10 30 50 70
Tree:
A
/ \
B C
/ \
D E
\ /
F G
Preorder:
A B D F C E G
Inorder:
D F B A C G E
Postorder:
F D B G E C A
Level-order:
A B C D E F G
Tree:
15
/ \
8 25
/ \ /
4 12 20
/ \
10 22
Preorder:
15 8 4 12 10 25 20 22
Inorder:
4 8 10 12 15 20 22 25
Complete inorder:
4 8 10 12 15 20 22 25
Postorder:
4 10 12 8 22 20 25 15
Level-order:
15 8 25 4 12 20 10 22
Result:
15 8 4 12 10 25 20 22
Result:
4 8 10 12 15 20 22 25
Because this is a Binary Search Tree, the inorder sequence is sorted.
Result:
4 10 12 8 22 20 25 15
Construct a BST by inserting:
50, 30, 70, 20, 40, 60, 80
Insert 50:
50
Insert 30:
30 < 50, so it goes left.
50
/
30
Insert 70:
70 > 50, so it goes right.
50
/ \
30 70
Insert 20:
20 < 50
20 < 30
Therefore, 20 becomes the left child of 30.
Insert 40:
40 < 50
40 > 30
Therefore, 40 becomes the right child of 30.
Insert 60:
60 > 50
60 < 70
Therefore, 60 becomes the left child of 70.
Insert 80:
80 > 50
80 > 70
Therefore, 80 becomes the right child of 70.
50
/ \
30 70
/ \ / \
20 40 60 80
Preorder:
50 30 20 40 70 60 80
Inorder:
20 30 40 50 60 70 80
Postorder:
20 40 30 60 80 70 50
Level-order:
50 30 70 20 40 60 80
The inorder traversal is in ascending order. This confirms the BST ordering property.
Construct a BST by inserting:
40, 20, 60, 10, 30, 50, 70, 25, 35
40
/ \
20 60
/ \ / \
10 30 50 70
/ \
25 35
Compare 25 with 40:
25 < 40, move left.
Compare 25 with 20:
25 > 20, move right.
Compare 25 with 30:
25 < 30, move left.
Find 25.
Search path:
40 β 20 β 30 β 25
Number of comparisons:
4
55 > 40, move right to 60.
55 < 60, move left to 50.
55 > 50, but 50 has no right child.
Result:
55 is not present.
Search path:
40 β 60 β 50 β NULL
Minimum = 10
Maximum = 70
Preorder:
40 20 10 30 25 35 60 50 70
Inorder:
10 20 25 30 35 40 50 60 70
Postorder:
10 25 35 30 20 50 70 60 40
Use this BST:
50
/ \
30 70
/ \ / \
20 40 60 80
\
65
Node 20 is a leaf.
Remove it directly:
50
/ \
30 70
\ / \
40 60 80
\
65
This is deletion of a node with zero children.
In the original tree, node 60 has one child, 65.
Connect the parent of 60 directly to 65:
50
/ \
30 70
/ \ / \
20 40 65 80
This is deletion of a node with one child.
In the original tree, node 50 has two children.
Its inorder successor is the smallest node in its right subtree:
Successor = 60
Replace 50 with 60. Then delete the original 60. Because the original 60 has one child, connect 65 to 70.
Result:
60
/ \
30 70
/ \ / \
20 40 65 80
Alternatively, the inorder predecessor 40 could be used if the question allows predecessor replacement.
Zero children β Remove
One child β Replace by child
Two children β Use predecessor or successor
Mnemonic:
Z-O-T
Zero, One, Two
Graph:
A ----- B
| |
| |
C ----- D ----- E
\ /
\-----------F
Adjacency list in alphabetical order:
A: B, C
B: A, D
C: A, D, F
D: B, C, E
E: D, F
F: C, E
Use a queue.
| Step | Visit | Newly Enqueued | Queue After Step |
|---|---|---|---|
| 1 | A | B, C | B, C |
| 2 | B | D | C, D |
| 3 | C | F | D, F |
| 4 | D | E | F, E |
| 5 | F | None; E already discovered | E |
| 6 | E | None | Empty |
BFS order:
A B C D F E
Use alphabetical neighbour order and recursive DFS.
DFS order:
A B D C F E
A graph may have more than one valid BFS or DFS order. The exact order depends on the order in which neighbours are selected.
The essential rules remain:
BFS β Level by level using a queue
DFS β Deep path first using a stack or recursion
Given:
Hash table size m = 10
Hash function h(k) = k mod 10
Insert:
23, 43, 13, 27, 37
Hash values:
h(23) = 3
h(43) = 3
h(13) = 3
h(27) = 7
h(37) = 7
Table:
| Index | Chain |
|---|---|
| 0 | β |
| 1 | β |
| 2 | β |
| 3 | 23 β 43 β 13 |
| 4 | β |
| 5 | β |
| 6 | β |
| 7 | 27 β 37 |
| 8 | β |
| 9 | β |
Insert 23:
h(23) = 3
Store at index 3.
Insert 43:
Index 3 is occupied.
Check index 4.
Store at index 4.
Insert 13:
Index 3 is occupied.
Index 4 is occupied.
Store at index 5.
Insert 27:
h(27) = 7
Store at index 7.
Insert 37:
Index 7 is occupied.
Store at index 8.
Final table:
| Index | Value |
|---|---|
| 0 | β |
| 1 | β |
| 2 | β |
| 3 | 23 |
| 4 | 43 |
| 5 | 13 |
| 6 | β |
| 7 | 27 |
| 8 | 37 |
| 9 | β |
Number of keys:
n = 5
Table size:
m = 10
Load factor:
Ξ± = n/m
= 5/10
= 0.5
Sort the following using different algorithms:
7, 4, 5, 2
Initial:
7, 4, 5, 2
Pass 1:
Compare 7 and 4 β Swap
4, 7, 5, 2
Compare 7 and 5 β Swap
4, 5, 7, 2
Compare 7 and 2 β Swap
4, 5, 2, 7
Pass 2:
Compare 4 and 5 β No swap
4, 5, 2, 7
Compare 5 and 2 β Swap
4, 2, 5, 7
Pass 3:
Compare 4 and 2 β Swap
2, 4, 5, 7
Sorted:
2, 4, 5, 7
Initial:
7, 4, 5, 2
Pass 1:
Smallest = 2
Swap 2 with 7
2, 4, 5, 7
Pass 2:
Smallest in 4, 5, 7 = 4
No effective change
2, 4, 5, 7
Pass 3:
Smallest in 5, 7 = 5
Sorted:
2, 4, 5, 7
Initial:
7 | 4, 5, 2
Insert 4 into the sorted part:
4, 7 | 5, 2
Insert 5:
4, 5, 7 | 2
Insert 2:
2, 4, 5, 7
Sorted:
2, 4, 5, 7
Sorted array:
| Index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| Value | 5 | 12 | 19 | 27 | 31 | 44 | 56 | 68 | 75 |
Search for 56.
low = 0
high = 8
mid = 0 + (8 β 0)/2
= 4
Value at index 4:
31
Since:
56 > 31
Move right:
low = 5
high = 8
mid = 5 + (8 β 5)/2
= 5 + 1
= 6
Value at index 6:
56
Result:
Target found at index 6.
Comparisons:
2
An algorithm performs one operation regardless of input size.
Answer:
O(1)
An algorithm checks every array element once.
Answer:
O(n)
An algorithm repeatedly halves the search area.
Answer:
O(log n)
An algorithm has two nested loops, each running n times.
Answer:
O(nΒ²)
An algorithm performs linear work at each level of a logarithmic recursion tree.
Answer:
O(n log n)
Simplify:
O(4nΒ² + 7n + 20)
Answer:
O(nΒ²)
The highest-growing term is nΒ². Constants and smaller terms are ignored.
| Term | Meaning |
|---|---|
| Root | Topmost node |
| Parent | Node directly above another node |
| Child | Node directly below another node |
| Siblings | Nodes with the same parent |
| Leaf | Node with no children |
| Internal node | Node with at least one child |
| Degree of node | Number of children |
| Depth | Edges from root to node |
| Height | Longest downward path in edges |
| Subtree | Node together with its descendants |
| Type | Rule |
|---|---|
| Binary | At most two children |
| Full | Every node has 0 or 2 children |
| Complete | Last level filled from left |
| Perfect | All internal nodes have 2 children; leaves at same level |
| Balanced | Height remains small |
| Skewed | Most nodes have one child |
Assume root level 0 and height in edges.
| Property | Formula |
|---|---|
Maximum nodes at level l | 2^l |
Maximum nodes for height h | 2^(h+1) β 1 |
Maximum leaves for height h | 2^h |
Minimum nodes for height h | h + 1 |
Edges in tree with n nodes | n β 1 |
| NULL child links in linked binary tree | n + 1 |
| Full tree leaves | L = I + 1 |
| Full tree total nodes | N = 2I + 1 |
| Relationship | Formula |
|---|---|
| Left child | 2i |
| Right child | 2i + 1 |
| Parent | floor(i/2) |
| Relationship | Formula |
|---|---|
| Left child | 2i + 1 |
| Right child | 2i + 2 |
| Parent | floor((i β 1)/2) |
| Traversal | Order | Memory Rule |
|---|---|---|
| Preorder | NLR | Node first |
| Inorder | LNR | Node in middle |
| Postorder | LRN | Node last |
| Level-order | Level by level | Uses queue |
Mnemonic:
PRE = Root before subtrees
IN = Root between subtrees
POST = Root after subtrees
Important BST fact:
Inorder traversal of a BST gives sorted ascending order.
BST rule:
Left subtree keys < Node key < Right subtree keys
| Operation | Balanced BST | Skewed BST |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
Deletion cases:
Zero children β Remove
One child β Connect parent to child
Two children β Replace with predecessor or successor
Mnemonic:
Z-O-T
Minimum:
Leftmost node
Maximum:
Rightmost node
| Term | Meaning |
|---|---|
| Vertex | Graph node |
| Edge | Connection between vertices |
| Degree | Number of touching edges in an undirected graph |
| In-degree | Incoming directed edges |
| Out-degree | Outgoing directed edges |
| Path | Sequence of connected vertices |
| Cycle | Path returning to its starting vertex |
| Connected graph | Every vertex is reachable |
| Weighted graph | Edges have cost, distance or weight |
Undirected graph rule:
Sum of degrees = 2E
Directed graph rules:
Sum of in-degrees = E
Sum of out-degrees = E
| Feature | Adjacency Matrix | Adjacency List |
|---|---|---|
| Space | O(VΒ²) | O(V + E) |
| Edge lookup | O(1) | Depends on degree |
| Best for | Dense graph | Sparse graph |
| Visit neighbours | O(V) | O(degree) |
Mnemonic:
Dense β Matrix
Sparse β List
| BFS | DFS |
|---|---|
| Breadth first | Depth first |
| Uses queue | Uses stack or recursion |
| Level by level | Deep path first |
| Finds shortest path in unweighted graph | Useful for backtracking and cycle detection |
| O(V + E) with adjacency list | O(V + E) with adjacency list |
Mnemonic:
BFS = Broad + Queue
DFS = Deep + Stack
Hashing process:
Key β Hash function β Table index
Collision:
Two different keys produce the same index.
Collision methods:
Formulas:
Load factor:
Ξ± = n/m
Linear probing:
hα΅’(k) = [h(k) + i] mod m
Quadratic probing:
hα΅’(k) = [h(k) + iΒ²] mod m
Double hashing:
hα΅’(k) = [hβ(k) + i Γ hβ(k)] mod m
Complexity:
Average search = O(1)
Worst search = O(n)
| Algorithm | Best | Average | Worst | Extra Space | Stable | In-Place |
|---|---|---|---|---|---|---|
| Bubble, optimized | O(n) | O(nΒ²) | O(nΒ²) | O(1) | Yes | Yes |
| Selection | O(nΒ²) | O(nΒ²) | O(nΒ²) | O(1) | No | Yes |
| Insertion | O(n) | O(nΒ²) | O(nΒ²) | O(1) | Yes | Yes |
| Quick | O(n log n) | O(n log n) | O(nΒ²) | O(log n) average stack | No | Usually yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Yes |
Stable sorts:
Bubble, Insertion, Merge
Mnemonic: BIM
Average O(nΒ²) simple sorts:
Bubble, Insertion, Selection
Mnemonic: BIS
Guaranteed O(n log n) worst case:
Merge, Heap
Mnemonic: MH
Dangerous worst case:
Quick Sort = O(nΒ²)
Nearly sorted input:
Insertion Sort
Few swaps:
Selection Sort
External sorting:
Merge Sort
| Feature | Linear Search | Binary Search |
|---|---|---|
| Sorted data required | No | Yes |
| Best | O(1) | O(1) |
| Average | O(n) | O(log n) |
| Worst | O(n) | O(log n) |
| Strategy | Check one by one | Repeatedly halve range |
Safe middle formula:
mid = low + (high β low)/2
Binary Search requirement:
Data must be sorted.
O(1)
<
O(log n)
<
O(n)
<
O(n log n)
<
O(nΒ²)
<
O(nΒ³)
<
O(2^n)
<
O(n!)
Examples:
| Complexity | Example |
|---|---|
| O(1) | Array access |
| O(log n) | Binary Search |
| O(n) | Linear Search |
| O(n log n) | Merge Sort |
| O(nΒ²) | Selection Sort |
| O(2^n) | Some recursive subset algorithms |
| O(n!) | Generating all permutations |
Which node in a tree has no parent?
A. Leaf node
B. Root node
C. Internal node
D. Sibling node
A tree has 20 nodes. How many edges does it have?
A. 18
B. 19
C. 20
D. 21
In a full binary tree, every node has:
A. Exactly one child
B. Zero or exactly two children
C. At most three children
D. Two children only, including leaves
Which statement correctly describes a complete binary tree?
A. Every leaf must be at the same level
B. Every node must have exactly two children
C. All levels except possibly the last are full, and the last is filled from left to right
D. Every node has only a right child
What is the maximum number of nodes in a binary tree of height 3 when height is measured in edges?
A. 7
B. 8
C. 15
D. 16
A full binary tree has 7 internal nodes. How many leaf nodes does it have?
A. 6
B. 7
C. 8
D. 14
For the following tree, what is its preorder traversal?
A
/ \
B C
/ \ \
D E F
A. D B E A C F
B. A B D E C F
C. D E B F C A
D. A C F B D E
For the same tree in Question 7, what is its inorder traversal?
A. A B D E C F
B. D B E A C F
C. D E B F C A
D. B D E A F C
For the same tree in Question 7, what is its postorder traversal?
A. D E B F C A
B. A B D E C F
C. D B E A C F
D. A C F B E D
Which traversal of a Binary Search Tree produces keys in ascending order?
A. Preorder
B. Inorder
C. Postorder
D. Level-order only
Insert the keys 40, 20, 60, 10, 30 into an empty BST. Which node becomes the right child of 20?
A. 10
B. 30
C. 40
D. 60
When deleting a BST node with two children, it can be replaced by:
A. Any random leaf
B. Only the root
C. Its inorder predecessor or inorder successor
D. The largest node in the entire tree in every case
Which graph representation normally uses O(VΒ²) space?
A. Adjacency list
B. Adjacency matrix
C. Linked stack
D. Binary heap
Which data structure is primarily used by Breadth-First Search?
A. Stack
B. Queue
C. Priority variable only
D. Binary Search Tree
Which data structure is used by iterative Depth-First Search?
A. Queue
B. Stack
C. Array index only
D. Hash function only
With an adjacency list, the time complexity of BFS or DFS is:
A. O(1)
B. O(log V)
C. O(V + E)
D. O(V Γ E) in every case
A collision in hashing occurs when:
A. A key is deleted
B. Two different keys produce the same table index
C. The table contains no keys
D. Binary Search is used
Given h(k) = k mod 10, which pair causes a collision?
A. 21 and 34
B. 15 and 29
C. 27 and 47
D. 11 and 12
Which sorting algorithm repeatedly selects the smallest element from the unsorted portion?
A. Bubble Sort
B. Selection Sort
C. Merge Sort
D. Quick Sort
Which sorting algorithm is usually the best simple choice for a small, nearly sorted array?
A. Insertion Sort
B. Selection Sort
C. Heap Sort only
D. Unoptimized Bubble Sort only
Which sorting algorithm has average O(n log n) time but worst-case O(nΒ²) time?
A. Merge Sort
B. Heap Sort
C. Quick Sort
D. Selection Sort
Which pair has guaranteed O(n log n) worst-case time?
A. Bubble Sort and Selection Sort
B. Merge Sort and Heap Sort
C. Insertion Sort and Quick Sort
D. Selection Sort and Quick Sort
Which sorting algorithm normally needs O(n) extra array space and is stable?
A. Heap Sort
B. Selection Sort
C. Merge Sort
D. Quick Sort
What is the most important requirement for Binary Search?
A. Data must be stored in a graph
B. Data must be sorted
C. Every value must be unique
D. Data must be in a linked list
Simplify the following time complexity:
T(n) = 4nΒ² + 7n + 100
A. O(1)
B. O(n)
C. O(nΒ²)
D. O(nΒ³)
| Q. | Answer | Q. | Answer | Q. | Answer | Q. | Answer | Q. | Answer |
|---|---|---|---|---|---|---|---|---|---|
| 1 | B | 6 | C | 11 | B | 16 | C | 21 | C |
| 2 | B | 7 | B | 12 | C | 17 | B | 22 | B |
| 3 | B | 8 | B | 13 | B | 18 | C | 23 | C |
| 4 | C | 9 | A | 14 | B | 19 | B | 24 | B |
| 5 | C | 10 | B | 15 | B | 20 | A | 25 | C |
The root is the topmost node. It has no parent.
A leaf has no children, but it normally has a parent unless the tree consists of only one node.
For any non-empty tree:
Edges = Nodes β 1
Therefore:
Edges = 20 β 1 = 19
A full binary tree does not allow a node with exactly one child.
Every node has:
A complete binary tree has every level full except possibly the last. The last level must be filled from left to right without an earlier gap.
Leaves do not all need to be at the same level. That stricter condition belongs to a perfect binary tree.
Maximum nodes at height h:
2^(h + 1) β 1
For height 3:
2^(3 + 1) β 1
= 2^4 β 1
= 16 β 1
= 15
For a full binary tree:
L = I + 1
Given:
I = 7
Therefore:
L = 7 + 1 = 8
A B D E C FPreorder follows:
Node β Left β Right
Visit A first, then Bβs subtree, and then Cβs subtree.
D B E A C FInorder follows:
Left β Node β Right
For the left subtree:
D B E
Then visit A.
For the right subtree:
C F
Complete sequence:
D B E A C F
D E B F C APostorder follows:
Left β Right β Node
The root A is visited last.
In a BST:
Left keys < Node key < Right keys
Therefore, inorder traversal visits the keys in ascending order.
Construction:
40 becomes root.
20 goes left of 40.
60 goes right of 40.
10 goes left of 20.
30 goes right of 20.
Therefore, 30 is the right child of 20.
For a node with two children, replace its value with:
Then delete the replacement node from its original position.
An adjacency matrix has one row and one column for every vertex.
Its size is:
V Γ V
Therefore, its space complexity is:
O(VΒ²)
BFS visits vertices level by level.
A queue preserves First In, First Out order, making it suitable for BFS.
DFS follows one path deeply before backtracking.
It uses:
With an adjacency list:
Therefore:
BFS = O(V + E)
DFS = O(V + E)
A collision occurs when two different keys produce the same hash-table index.
Example:
h(k) = k mod 10
h(27) = 7
h(47) = 7
Using:
h(k) = k mod 10
Calculations:
h(27) = 7
h(47) = 7
Both keys map to index 7.
Selection Sort finds the smallest element in the unsorted portion and places it at the beginning of that portion.
Insertion Sort is adaptive and efficient for:
Its best-case time is O(n).
Quick Sort complexities:
Best = O(n log n)
Average = O(n log n)
Worst = O(nΒ²)
The worst case occurs when partitions are repeatedly very unbalanced.
Both provide:
Worst-case time = O(n log n)
Quick Sort does not give this guarantee because its worst case is O(nΒ²).
Standard array-based Merge Sort:
Binary Search compares the target with the middle value and discards half of the search area.
This decision is only reliable when the data is sorted.
Given:
4nΒ² + 7n + 100
The highest-growing term is:
nΒ²
Drop constant multipliers and lower-order terms:
O(nΒ²)
1
/ \
2 3
/ \ / \
4 5 6 7
This tree is:
1
/ \
2 3
/ \
4 5
This tree is:
1
/
2
/
3
This tree is:
A perfect binary tree has height 4, measured in edges.
2^(h + 1) β 1
= 2^5 β 1
= 31
2^h
= 2^4
= 16
2^h β 1
= 16 β 1
= 15
Nodes β 1
= 31 β 1
= 30
Use one-based indexing.
A node is stored at index 6.
Find:
Parent:
floor(6/2) = 3
Left child:
2 Γ 6 = 12
Right child:
2 Γ 6 + 1 = 13
Tree:
M
/ \
H T
/ \ / \
D J P W
Preorder:
M H D J T P W
Inorder:
D H J M P T W
Postorder:
D J H P W T M
Level-order:
M H T D J P W
Insert:
45, 25, 65, 15, 35, 55, 75, 30
45
/ \
25 65
/ \ / \
15 35 55 75
/
30
15 25 30 35 45 55 65 75
45 β 25 β 35 β 30
15
75
Use:
40
/ \
20 60
/ \ / \
10 30 50 70
| Node Deleted | Case |
|---|---|
| 10 | Leaf or zero-child case |
| 20 after deleting 10 | One-child case |
| 40 in original tree | Two-child case |
For deleting 40, possible replacements are:
Predecessor = 30
Successor = 50
Graph edges:
AβB
AβC
BβC
CβD
Adjacency matrix:
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 0 | 0 | 1 | 0 |
Degrees:
Degree(A) = 2
Degree(B) = 2
Degree(C) = 3
Degree(D) = 1
Sum:
2 + 2 + 3 + 1 = 8
Edges:
E = 4
Check:
2E = 8
The handshaking rule is satisfied.
Graph adjacency list:
A: B, C
B: A, D, E
C: A, F
D: B
E: B, F
F: C, E
Starting at A and using alphabetical neighbour order:
A B C D E F
A B D E F C
Remember:
BFS uses a queue.
DFS uses a stack or recursion.
Given:
Table size = 7
h(k) = k mod 7
Insert:
10, 17, 24, 31
Hash values:
10 mod 7 = 3
17 mod 7 = 3
24 mod 7 = 3
31 mod 7 = 3
Using linear probing:
| Key | Initial Index | Final Index |
|---|---|---|
| 10 | 3 | 3 |
| 17 | 3 | 4 |
| 24 | 3 | 5 |
| 31 | 3 | 6 |
Final table:
| Index | Value |
|---|---|
| 0 | β |
| 1 | β |
| 2 | β |
| 3 | 10 |
| 4 | 17 |
| 5 | 24 |
| 6 | 31 |
This consecutive group demonstrates primary clustering.
| Description | Algorithm |
|---|---|
| Compares adjacent elements | Bubble Sort |
| Selects smallest remaining element | Selection Sort |
| Inserts next element into sorted part | Insertion Sort |
| Partitions around a pivot | Quick Sort |
| Divides and merges sorted halves | Merge Sort |
| Uses a complete binary heap | Heap Sort |
Complete from memory:
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Bubble, optimized | O(n) | O(nΒ²) | O(nΒ²) |
| Selection | O(nΒ²) | O(nΒ²) | O(nΒ²) |
| Insertion | O(n) | O(nΒ²) | O(nΒ²) |
| Quick | O(n log n) | O(n log n) | O(nΒ²) |
| Merge | O(n log n) | O(n log n) | O(n log n) |
| Heap | O(n log n) | O(n log n) | O(n log n) |
Bubble Sort
Insertion Sort
Merge Sort
Mnemonic:
BIM
Bubble Sort
Selection Sort
Insertion Sort
Quick Sort, in common array implementations
Heap Sort
Standard array-based Merge Sort is not in-place because it normally needs O(n) extra memory.
Array:
18, 4, 27, 9, 31
Search for 9.
Comparisons:
18 β No
4 β No
27 β No
9 β Found
Comparisons:
4
Linear Search works even though the array is unsorted.
Sorted array:
10, 20, 30, 40, 50, 60, 70, 80
Search for 70.
Possible trace with indices 0 to 7:
low = 0, high = 7
mid = 3, value = 40
70 > 40, search right.
low = 4, high = 7
mid = 5, value = 60
70 > 60, search right.
low = 6, high = 7
mid = 6, value = 70
Found.
Comparisons:
3
| Expression | Simplified Complexity |
|---|---|
7 | O(1) |
3n + 10 | O(n) |
2nΒ² + 5n + 1 | O(nΒ²) |
n log n + n | O(n log n) |
4nΒ³ + nΒ² | O(nΒ³) |
2^n + nΒ² | O(2^n) |
n nodes?l?h?h?n loops?5nΒ² + 3n + 20?Use your score from the 25 MCQs.
| Correct Answers | Level | Required Action |
|---|---|---|
| 23β25 | Excellent | Revise the complexity table tomorrow |
| 20β22 | Good | Review incorrect answers and redo traversal tests |
| 16β19 | Developing | Repeat BST, graph traversal and sorting complexities |
| 10β15 | Weak | Restudy all five hourly sections |
| 0β9 | Beginning | Read the material again slowly from the start |
| Questions Missed | Topic to Revise |
|---|---|
| 1β6 | Tree terminology, types and properties |
| 7β12 | Traversals and Binary Search Trees |
| 13β18 | Graphs, BFS, DFS and hashing |
| 19β23 | Sorting algorithms and complexities |
| 24β25 | Binary Search and Big-O |
Study:
Write from memory:
Maximum nodes at level l = 2^l
Maximum nodes at height h = 2^(h+1) β 1
Maximum leaves at height h = 2^h
Edges = n β 1
Full tree: L = I + 1
Practice:
Study:
Memorize:
Preorder = NLR
Inorder = LNR
Postorder = LRN
Practice:
Study:
Memorize:
Dense β Matrix
Sparse β List
BFS β Queue
DFS β Stack
Practice:
Study and trace:
Write the complete complexity table from memory.
Memorize:
Stable = Bubble, Insertion, Merge
Average O(nΒ²) simple sorts = Bubble, Insertion, Selection
Guaranteed O(n log n) worst case = Merge, Heap
Quick worst case = O(nΒ²)
Practice sorting:
8, 3, 6, 1, 5
Use:
Then explain conceptually how Quick, Merge and Heap Sort would process it.
Study:
Practice:
Full tree:
Every node has 0 or 2 children
Complete tree:
Last level filled from left
Perfect tree:
All internal nodes have 2 children
All leaves at same level
Maximum nodes at level l:
2^l
Maximum nodes at height h:
2^(h+1) β 1
Tree edges:
n β 1
Preorder:
NLR
Inorder:
LNR
Postorder:
LRN
BST inorder:
Sorted order
BST deletion:
Zero, One, Two children
Dense graph:
Adjacency matrix
Sparse graph:
Adjacency list
BFS:
Queue
DFS:
Stack or recursion
BFS and DFS:
O(V + E) with adjacency list
Hash collision:
Different keys, same index
Bubble:
Adjacent swaps
Selection:
Select minimum
Insertion:
Insert into sorted part
Quick:
Pivot and partition
Merge:
Divide and merge
Heap:
Build heap and repeatedly remove root
Stable:
Bubble, Insertion, Merge
Quick worst:
O(nΒ²)
Merge and Heap worst:
O(n log n)
Linear Search:
O(n)
Binary Search:
O(log n)
Requires sorted data
Big-O order:
1 < log n < n < n log n < nΒ² < nΒ³ < 2^n < n!