KTU BBA & BCA UPDATES

Your trusted community for KTU BBA & BCA notes,

question papers and university updates.

Join our WhatsApp Community

Click here to join

NOTES | SYLLABUS | ANNOUNCEMENTS | QUESTION BANKS |

TIMETABLES | STUDY RESOURCES

🌐Website
[Link]

Contact us
✉︎ ktubbabcaupdates@[Link]
✆ 9544136946
Chapter 2

Divide and Conquer and Graph Algorithms

2.1 Divide and Conquer

The Divide and Conquer Algorithm is a problem-solving technique used to solve complex
problems by dividing them into smaller, independent subproblems, solving each subproblem
individually, and then combining their solutions to form the final answer.
It is particularly effective when the subproblems are independent (do not overlap). If
the subproblems overlap, we use Dynamic Programming instead.

Working of Divide and Conquer Algorithm

The Divide and Conquer approach can be divided into three main steps:

1. Divide
• Break the main problem into smaller subproblems.

• Each subproblem represents a specific portion of the overall problem.

• Continue dividing until no further division is possible (base case).

Example: In Merge Sort, the array is divided into two halves. In Quick Sort, the array
is divided around a pivot element.

2. Conquer
• Solve each smaller subproblem individually.

33
34 2.1. DIVIDE AND CONQUER

• When a subproblem becomes simple enough, solve it directly without further recursion.

Example: In Merge Sort, each half is sorted individually.

3. Merge
• Combine the solutions of the subproblems to form the final solution.

• The merging step must be efficient and correctly integrate sub-solutions.

Example: In Merge Sort, the two sorted halves are merged to form a completely sorted
array.

Characteristics of Divide and Conquer Algorithm

1. Dividing the Problem: The problem is recursively divided into smaller subproblems
until they become simple enough to solve directly.

2. Independence of Subproblems: Each subproblem should be independent, allowing

parallel or concurrent execution for improved efficiency.

3. Conquering Each Subproblem: Each subproblem is solved individually, often using

recursion.

4. Combining Solutions: The solutions of the subproblems are combined to form the
final answer to the original problem.

Examples of Divide and Conquer Algorithms

• Merge Sort

• Quick Sort

• Binary Search

• Strassen’s Matrix Multiplication

• Closest Pair of Points Problem

CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 35

2.1.1 Binary Search

Binary Search is a searching algorithm that works on a sorted (or monotonic) search space
by repeatedly dividing the search interval in half and discarding the half that cannot contain
the target. It runs in logarithmic time, O(log n), when applied to random-access structures
like arrays.

Conditions
• The data structure must be sorted.

• Random access to elements should be available (constant time access).

Binary Search as Divide & Conquer

Divide:
Compute the middle index and split the search interval into two halves.

Conquer:
Compare the key with the middle element and select the half to continue searching.

Merge:
Trivial — no nontrivial merge is required; the result is either the element found or not
found.

Algorithm (High Level)

Initialize low = 0, high = n − 1. Repeat:

high − low
$ %
mid = low + .
2

Compare A[mid] with the key and update low or high accordingly until the key is found or
the interval is empty.
36 2.1. DIVIDE AND CONQUER

Worked Example: Binary Search as Divide and Conquer

Let
arr = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, target = 23.

Indices range from 0 to 9.

Step Low High Mid Operation and Comparison

0+9 arr[4] = 16 ⇒ 23 > 16, so search

 
=
1 0 9 2 the right half
4 New range: low = 5, high = 9.

5+9 arr[7] = 56 ⇒ 23 < 56, so search

 
=
2 5 9 2 the left half
7 New range: low = 5, high = 6.
5+6
 
= arr[5] = 23 ⇒ 23 = 23, Target
3 5 6 2
5 found at index 5.

Table 2.1: Step-by-step working of Binary Search algorithm.

Result: Element 23 found at index 5.

Total comparisons: 3
Time Complexity: O(log2 n), since the array is divided into halves at each step.
Space Complexity: O(1) for iterative version, O(log n) for recursive version. Total com-
parisons in this run: 3. (Worst-case for n = 10 is ⌊log2 10⌋ + 1 = 4.)

Complexity analysis
Let C(n) denote the worst-case number of comparisons on an array of size n.

C(1) = 1, C(n) = 1 + C(⌊n/2⌋) for n > 1.

The recurrence halves n each time. The number k of halvings to reach 1 is k = ⌊log2 n⌋.
Hence
C(n) = ⌊log2 n⌋ + 1.

Thus time complexity is Θ(log n) (worst and average). Space complexity is O(1) for the
iterative version, and O(log n) for the recursive version (recursion stack).
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 37

Pseudocode (iterative)

Algorithm 1 Iterative Binary Search

1: procedure BinarySearch(A, n, key)
2: low ← 0
3: high ← n - 1
4: while low ≤ high do
5: mid ← low + ⌊(high − low)/2⌋
6: if A[mid] == key then
7: return mid
8: else if key < A[mid] then
9: high ← mid - 1
10: else
11: low ← mid + 1
12: end if
13: end while
14: return NOT_FOUND
15: end procedure

2.1.2 Merge Sort

Merge Sort is a stable, comparison-based sorting algorithm that follows the Divide and
Conquer paradigm. It recursively divides the input array into two halves, sorts each half,
and merges the two sorted halves to produce the final sorted array.

Divide & Conquer Steps

• Divide: Split the input array into two halves.

• Conquer: Recursively sort each half.

• Combine: Merge the two sorted halves into a single sorted array.

Algorithm: Merge Sort

Worked Example
Sort the array {38, 27, 43, 10}.
38 2.1. DIVIDE AND CONQUER

Algorithm 2 MergeSort(A, left, right)

1: if left < right then
2: mid ← ⌊ (left + right)/2 ⌋
3: MergeSort(A, left, mid) ▷ Sort the left half
4: MergeSort(A, mid + 1, right) ▷ Sort the right half
5: Merge(A, left, mid, right) ▷ Merge the two halves
6: end if

Algorithm 3 Merge(A, left, mid, right)

1: Create temporary arrays:
L = A[lef t . . . mid], R = A[mid + 1 . . . right]
2: Initialize i = 0, j = 0, k = lef t
3: while i < |L| and j < |R| do
4: if L[i] ≤ R[j] then
5: A[k] ← L[i]
6: i←i+1
7: else
8: A[k] ← R[j]
9: j ←j+1
10: end if
11: k ←k+1
12: end while
13: while i < |L| do
14: A[k] ← L[i]
15: i←i+1
16: k ←k+1
17: end while
18: while j < |R| do
19: A[k] ← R[j]
20: j ←j+1
21: k ←k+1
22: end while

1. Divide into [38, 27] and [43, 10].

2. Further divide: [38], [27], [43], [10].

3. Merge pairs:

• Merge [38] and [27] ⇒ [27, 38].

• Merge [43] and [10] ⇒ [10, 43].

• Merge [27, 38] and [10, 43] ⇒ [10, 27, 38, 43].
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 39

Final sorted array: [10, 27, 38, 43].

Recurrence Relation

Θ(1), n = 1,


T (n) = n
 
2T + Θ(n), n > 1.


2

Solving Using the Master Theorem

Given T (n) = aT (n/b) + f (n) where a = 2, b = 2, f (n) = Θ(n):

nlogb a = nlog2 2 = n.

Since f (n) = Θ(n) = Θ(nlogb a ), we apply Case 2 of the Master Theorem:

T (n) = Θ(n log n).

Complexity Analysis
• Time Complexity:

– Best Case: O(n log n)

– Average Case: O(n log n)
– Worst Case: O(n log n)

• Space Complexity: O(n) extra space (not in-place)

• Stability: Stable sorting algorithm

Advantages
• Stable and guarantees O(n log n) even in worst case.

• Simple recursive divide-and-conquer structure.

• Suitable for parallel processing since halves are independent.

40 2.1. DIVIDE AND CONQUER

Disadvantages

• Requires extra memory (O(n)).

• Slower than in-place algorithms like QuickSort on small datasets.

2.1.3 Quick Sort

Quick Sort is a highly efficient sorting algorithm that follows the Divide and Conquer
approach. It works by selecting a pivot element and partitioning the array such that all
elements less than or equal to the pivot are moved to its left and those greater than the
pivot are moved to its right. The process is recursively applied to both subarrays until the
entire array is sorted.
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 41

Algorithm (Pseudocode)

Algorithm 4 Quick Sort

1: procedure QUICKSORT(A, low, high)
2: if low < high then
3: pivot_index ← PARTITION(A, low, high)
4: QUICKSORT(A, low, pivot_index - 1)
5: QUICKSORT(A, pivot_index + 1, high)
6: end if
7: end procedure
8:
9: procedure PARTITION(A, low, high)
10: pivot ← A[high]
11: i ← low - 1
12: for j ← low to high - 1 do
13: if A[j] ≤ pivot then
14: i←i+1
15: swap(A[i], A[j])
16: end if
17: end for
18: swap(A[i + 1], A[high])
19: return i + 1
20: end procedure

Step-by-Step Example
Let us sort the array [11, 9, 12, 7, 3] using Quick Sort.

Step 1: Start: Unsorted array [11, 9, 12, 7, 3].

Step 2: Choose Pivot: Last element 3 as pivot. All other values are greater than 3, so
they move to the right. Swap 3 with 11:

[3, 9, 12, 7, 11]

Now, 3 is in the correct position.

Step 3: Sort Right Subarray: Subarray [9, 12, 7, 11] is selected. Choose pivot 11.
42 2.1. DIVIDE AND CONQUER

Step 4: Partition:

• 9 < 11 (left side)

• 12 > 11 (right side)

• 7 < 11 (left side)

Swap 7 and 12 to correct positions:

[3, 9, 7, 12, 11]

Swap pivot 11 with 12:

[3, 9, 7, 11, 12]

Now, 11 and 12 are in correct positions.

Step 5: Sort Left Subarray: Consider subarray [9, 7] to the left of 11. Choose pivot 7.

Step 6: Swap: Since 9 > 7, swap them:

[3, 7, 9, 11, 12]

Now, the array is completely sorted.

Final Sorted Array: [3, 7, 9, 11, 12]

Recurrence Relation
Let T (n) represent the time required to sort an array of size n. Then:

T (n) = T (k) + T (n − k − 1) + Θ(n)

where k is the number of elements smaller than the pivot.

Analysis Using Master’s Theorem

Best Case: Pivot divides the array evenly.

n
 
T (n) = 2T + Θ(n)
2
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 43

By Master’s Theorem:

a = 2, b = 2, f (n) = Θ(n) ⇒ T (n) = Θ(n log n)

Worst Case: Pivot divides as (n − 1) and (0).

T (n) = T (n − 1) + Θ(n) = Θ(n2 )

Average Case:
T (n) = O(n log n)

Complexity Analysis

Case Time Complexity Space Complexity

Best Case O(n log n) O(log n)
Average Case O(n log n) O(log n)
Worst Case O(n2 ) O(log n)

Advantages
• Efficient for large datasets with average-case time complexity of O(n log n).

• In-place sorting algorithm; requires minimal additional memory.

• Cache-friendly and easily optimized with tail recursion.

• Performs well for average input distributions.

Disadvantages
• Worst-case complexity of O(n2 ) if pivot selection is poor.

• Not a stable sorting algorithm.

• Recursive implementation may cause stack overflow for large inputs.

2.2 Graph Theory

Graph Theory is a branch of mathematics that studies the properties and applications of
graphs. A graph is a collection of vertices (also called nodes) connected by edges (also
44 2.2. GRAPH THEORY

called links). Graphs are used to model pairwise relations between objects, making them a
powerful tool for representing and analyzing complex systems in various fields.

Definition of a Graph
A graph G can be defined as an ordered pair:

G = (V, E)

where:

• V is a set of vertices.

• E is a set of edges, where each edge is a pair of vertices from V .

For example, let:

V = {a, b, c, d, e, f }, E = {ab, af, bc, cd, de, ef }

Real-Life Examples of Graphs

• Social Networks: Vertices represent people, and edges represent friendships.

• Transportation Networks: Vertices represent locations, and edges represent routes

or connections.

• Computer Networks: Vertices represent computers or devices, and edges represent

communication links.

Undirected Graph
An undirected graph is a type of graph in which the edges have no direction. This means
that the relationship between any pair of connected vertices is mutual. In an undirected
graph, the edge (u, v) is identical to the edge (v, u).
Example:

V = {A, B, C, D}, E = {{A, B}, {A, C}, {B, D}, {C, D}}
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 45

A B

C D

Directed Graph (Digraph)

A directed graph (or digraph) is a type of graph where each edge has a direction. Each
edge has a starting vertex (source) and an ending vertex (destination), indicating a one-way
relationship between the vertices.
Example:

V = {A, B, C, D}, E = {(A, B), (A, C), (B, D), (C, D)}

A B

C D

Weighted Graph
A weighted graph assigns a weight to each edge representing cost, distance, or capacity.

V = {A, B, C, D}, E = {(A, B, 3), (A, C, 5), (B, D, 2), (C, D, 1)}

3
A B

5 2

C D
1
46 2.3. GRAPH TRAVERSAL

2.3 Graph Traversal

Graph traversal is the process of visiting all vertices of a graph systematically. It is used for:

• Searching a node

• Detecting cycles

• Finding shortest paths

• Computing connected components

The two main traversal techniques are:

1. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

Depth-First Search (DFS)

DFS explores a graph deeply, visiting all vertices reachable through a neighbor before
moving to the next neighbor. It starts at a source node and explores as far as possible along
each branch before backtracking.

DFS Algorithm (Recursive)

DFS(graph, root):
create a visited set
call DFS-Visit(graph, root, visited)

DFS-Visit(graph, node, visited):

mark node as visited
process(node)

for each neighbor of node in graph:

if neighbor is not visited:
DFS-Visit(graph, neighbor, visited)
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 47

Step-by-Step Explanation
1. Start at a vertex v. 2. Mark it as visited. 3. For each unvisited neighbor, recursively
perform DFS. 4. Backtrack when no unvisited neighbors remain. 5. Repeat until all vertices
are visited.

Time Complexity of DFS

• Node Processing: Each vertex is visited exactly once ⇒ O(V )

• Edge Processing: Each edge is explored once ⇒ O(E)

• Overall: O(V + E) for adjacency list representation

DFS Example
Graph:
A

B C

D E

DFS Traversal Order: A → B → D → E → C

—

Breadth-First Search (BFS)

BFS explores a graph level by level using a queue. It visits all neighbors of a vertex before
moving to the next level.

BFS Algorithm
BFS(graph, start):
create a visited set
create a queue and enqueue start
mark start as visited
48 2.3. GRAPH TRAVERSAL

while queue is not empty:

vertex = dequeue from queue
process(vertex)
for each neighbor of vertex:
if neighbor is not visited:
enqueue neighbor
mark neighbor as visited

Step-by-Step Explanation
1. Start at a vertex v. 2. Mark it visited and enqueue it. 3. While queue is not empty: -
Dequeue a vertex u - Visit all unvisited neighbors, mark them, and enqueue them 4. Repeat
until all vertices are visited

Time Complexity of BFS

- Each vertex is visited once → O(V ) - Each edge is processed once → O(E) - Overall BFS
complexity: O(V + E)

BFS Example
Graph:
A

B C

D E

BFS Traversal Order: A → B → C → D → E

—

5. Summary
• DFS uses recursion or stack → explores deep paths first

• BFS uses queue → explores level by level

• Both DFS and BFS have time complexity O(V + E) for adjacency list representation
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 49

• Traversal is fundamental for searching, cycle detection, path finding, and connected
components

2.3.1 Topological Sorting

Topological sorting for a Directed Acyclic Graph (DAG) is a linear ordering of vertices such
that for every directed edge u → v, vertex u comes before v in the ordering.
Note: Topological Sorting is only possible for DAGs. If the graph contains cycles,
topological sorting cannot be performed.

2.4 Algorithm for Topological Sorting using DFS

Let G = (V, E) be a graph with n vertices and m directed edges. The algorithm proceeds
as follows:

1. Create a graph with n vertices and m directed edges.

2. Initialize a stack and a visited array of size n with all values set to false.

3. For each unvisited vertex v in the graph, perform the following:

(a) Call the DFS function with v as the parameter.

(b) In the DFS function:
i. Mark v as visited.
ii. Recursively call DFS for all unvisited neighbors of v.
iii. After visiting all neighbors, push v onto the stack.

4. Once all vertices are visited, pop elements from the stack and append them to the
output list.

5. The resulting list is the topologically sorted order of the graph.

2.5 Pseudocode
TopologicalSort(Graph G):
stack = empty
visited = [False]*n
50 2.6. EXAMPLE AND VISUALIZATION

for each vertex v in G:

if not visited[v]:
DFS(v, visited, stack)

topological_order = []
while stack is not empty:
topological_order.append([Link]())
return topological_order

DFS(v, visited, stack):

visited[v] = True
for each neighbor u of v:
if not visited[u]:
DFS(u, visited, stack)
[Link](v)

2.6 Example and Visualization

Consider the following DAG:

1 2 3

4 5

2.6.1 Step-by-Step Execution

1. Start DFS from vertex 1:

• Visit 1, then 2.

• Visit 3 from 2, backtrack.

• Visit 4 from 1, then 5, then 3 (already visited).

2. Stack after DFS: [3, 2, 5, 4, 1]

CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 51

3. Pop elements from stack to get topological order:

1, 4, 5, 2, 3

2.6.2 Dijkstra’s Algorithm

Dijkstra’s algorithm, conceived by Dutch computer scientist Edsger W. Dijkstra in 1956, is
a cornerstone of graph theory. It provides a method for finding the shortest paths between
nodes in a weighted graph. A common application is finding the shortest route between two
points, like in a GPS navigation system. The algorithm works for graphs with non-negative
edge weights. It operates by building a set of nodes for which the shortest path from the
source is known and final.

2.7 Algorithm
Dijkstra’s algorithm follows a greedy approach. It always picks the unvisited vertex with
the smallest known distance to the source and marks it as visited. Then, it updates the
distances of its unvisited neighbors. This process continues until all vertices are visited.
The steps of the algorithm are as follows:

1. Initialization:

• Create a set of unvisited nodes, initially containing all nodes.

• Assign a tentative distance value to every node: set it to zero for our initial node
and to infinity for all other nodes.
• Set the initial node as the current node.

2. Iteration:

• For the current node, consider all of its unvisited neighbors.

• For each unvisited neighbor, calculate the tentative distance through the current
node.
• Compare the newly calculated tentative distance to the current assigned value
and assign the smaller one. For example, if the current node A is marked with
a distance of 6, and the edge connecting it with a neighbor B has length 2, then
the distance to B through A will be 6 + 2 = 8. If B was previously marked with
a distance greater than 8, then change it to 8. Otherwise, keep the current value.
52 2.8. WORKED EXAMPLE

3. Mark as Visited: When we are done considering all of the unvisited neighbors of the
current node, mark the current node as visited and remove it from the unvisited set.
A visited node will not be checked again.

4. Select Next Node: If the destination node has been marked visited (when planning
a route between two specific nodes) or if the smallest tentative distance among the
nodes in the unvisited set is infinity (when planning a complete traversal), then stop.
The algorithm has finished. Otherwise, select the unvisited node that is marked with
the smallest tentative distance, set it as the new "current node", and go back to step
2.

2.8 Worked Example

Let’s find the shortest path from node A to all other nodes in the following graph:

B
4 5

A 1 D

2
2 8
C E
10

We will use a table to keep track of the distances and the previous node in the shortest
path.

2.8.1 Step-by-Step Execution

Initialization

• Unvisited set: {A, B, C, D, E}

• Distances: A=0, B=∞, C=∞, D=∞, E=∞

• Current node: A
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 53

Iteration 1

• Current Node: A (distance 0)

• Neighbors of A: B, C

– Distance to B: 0 + 4 = 4. Update B’s distance to 4 (previous: A).

– Distance to C: 0 + 2 = 2. Update C’s distance to 2 (previous: A).

• Mark A as visited.

• New Distances: A=0, B=4, C=2, D=∞, E=∞

• Next Node: C (smallest distance among unvisited)

Iteration 2

• Current Node: C (distance 2)

• Neighbors of C: B, D, E

– Distance to B: 2 + 1 = 3. Update B’s distance to 3 (previous: C).

– Distance to D: 2 + 8 = 10. Update D’s distance to 10 (previous: C).
– Distance to E: 2 + 10 = 12. Update E’s distance to 12 (previous: C).

• Mark C as visited.

• New Distances: A=0, B=3, C=2, D=10, E=12

• Next Node: B (smallest distance among unvisited)

Iteration 3

• Current Node: B (distance 3)

• Neighbors of B: D

– Distance to D: 3 + 5 = 8. Update D’s distance to 8 (previous: B).

• Mark B as visited.

• New Distances: A=0, B=3, C=2, D=8, E=12

• Next Node: D (smallest distance among unvisited)

54 2.9. VISUALIZATION

Iteration 4

• Current Node: D (distance 8)

• Neighbors of D: E

– Distance to E: 8 + 2 = 10. Update E’s distance to 10 (previous: D).

• Mark D as visited.

• New Distances: A=0, B=3, C=2, D=8, E=10

• Next Node: E (smallest distance among unvisited)

Iteration 5

• Current Node: E (distance 10)

• No unvisited neighbors.

• Mark E as visited.

2.8.2 Final Shortest Paths

The algorithm is finished. The shortest distances from A are:

• A to A: 0

• A to B: 3 (Path: A -> C -> B)

• A to C: 2 (Path: A -> C)

• A to D: 8 (Path: A -> C -> B -> D)

• A to E: 10 (Path: A -> C -> B -> D -> E)

2.9 Visualization
The final shortest path tree can be visualized as follows. The red edges indicate the shortest
paths from the source node A to all other nodes.
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 55

A D

C E

2.10 AVL Tree Basics

An AVL (Adelson-Velsky and Landis) tree is a self-balancing binary search tree (BST). The
height difference between the left and right subtrees for any node, called the **balance
factor**, is at most 1. This property ensures that the tree remains balanced, preventing it
from becoming skewed. A balanced tree guarantees that operations like search, insertion,
and deletion have a worst-case time complexity of O(log n), where n is the number of nodes.

2.11 Properties
• It is a binary search tree.

• The heights of the two child subtrees of any node differ by at most one.

• The balance factor of a node is calculated as:

Balance Factor = height(left subtree) − height(right subtree)

• A node’s balance factor can be -1, 0, or 1. If it becomes something else, the tree needs
to be rebalanced.

2.12 Rotations
When an insertion or deletion causes the tree to become unbalanced, we perform rotations
to restore the AVL property. There are four types of rotations:
56 2.12. ROTATIONS

2.12.1 LL Rotation (Right Rotation)

This rotation is performed when a new node is inserted into the left subtree of the left child
of a node, causing an imbalance.

C B

Right Rotate(C)
B A C

AUnbalanced Tree Balanced Tree

2.12.2 RR Rotation (Left Rotation)

This rotation is performed when a new node is inserted into the right subtree of the right
child of a node.

A B

Left Rotate(A)
B A C

Unbalanced TreeC Balanced Tree

2.12.3 LR Rotation (Left-Right Rotation)

This rotation is a combination of a left rotation followed by a right rotation. It’s used when
a new node is inserted into the right subtree of the left child.

C C B

Left Rotate(A) Right Rotate(C)

A B A C

Unbalanced
B Tree A Balanced Tree
CHAPTER 2. DIVIDE AND CONQUER AND GRAPH ALGORITHMS 57

2.12.4 RL Rotation (Right-Left Rotation)

This rotation is a combination of a right rotation followed by a left rotation. It’s used when
a new node is inserted into the left subtree of the right child.

A A B

Right Rotate(C) Left Rotate(A)

C B A C

Unbalanced
B Tree C Balanced Tree

2.13 Worked Example: Insertion

Let’s insert the following keys into an empty AVL tree: 10, 20, 30, 40, 50, 25.

• Insert 10: The tree is just the node 10.

• Insert 20: 20 is greater than 10, so it becomes the right child. The tree is balanced.

• Insert 30: 30 is greater than 20. The tree becomes unbalanced at node 10 (balance
factor = -2). This is an RR case. We perform a left rotation on 10.

10 20
Left Rotate(10)

20 10 30

30

• Insert 40: Inserted as the right child of 30. The tree remains balanced.

• Insert 50: Inserted as the right child of 40. The tree becomes unbalanced at node 30
(balance factor = -2). This is another RR case. We perform a left rotation on 30. The
final tree after this step and inserting 40 is:
58 2.13. WORKED EXAMPLE: INSERTION

20

10 40

30 50

• Insert 25: Inserted as the left child of 30. Now, the tree is unbalanced at node 20
(balance factor = -2). The path is 20(right) -> 40(left) -> 30(right) -> 25. This is an
RL case. We first perform a right rotation on 40, and then a left rotation on 20.

30

20 40

10 25 50
Final Tree after inserting 25: