Module 3

Recursion and Trees

Definition of Recursion

Recursion in data structures is a programming technique where a function calls itself to solve a
problem.

The principle of recursion in data structures involves defining and solving problems by breaking
them down into smaller, self-similar subproblems until a simple base case is reached. The
solution to the original problem is then constructed from the solutions of these subproblems.

Key principles of recursion:

 Base Case:
Every recursive function or definition must have one or more base cases. This is the simplest
instance of the problem that can be solved directly without further recursion. The base case
serves as the termination condition, preventing infinite recursion.
 Recursive Case:
The recursive case defines how the problem for a larger input is expressed in terms of the same
problem for a smaller input. It involves a recursive call to the same function or definition, but
with parameters that move closer to the base case.
 Divide and Conquer:
Recursion often embodies the "divide and conquer" strategy, where a complex problem is
divided into smaller, identical subproblems. Each subproblem is solved using the same
recursive approach, and the results are combined to solve the original problem.
 Call Stack:
Recursion relies on the call stack to manage the sequence of function calls. Each time a
recursive function is called, a new stack frame is pushed onto the call stack, storing local
variables and the return address. When a base case is reached, functions return their results,
and their corresponding stack frames are popped, unwinding the recursion.
Examples in Data Structures:

 Tree Traversal:
Algorithms like Depth-First Search (DFS) for traversing trees (e.g., pre-order, in-order, post-
order) are naturally recursive, visiting a node and then recursively visiting its children.
 Linked Lists:
 Operations like reversing a linked list or searching for an element can be implemented
recursively.
 Sorting Algorithms:
Merge Sort and Quick Sort are prominent examples of recursive sorting algorithms that
repeatedly divide the data into smaller parts and then combine the sorted parts.

Recursive Function Works Internally

 Every time a function is called, a new stack frame is created in memory (on the call
stack).
 This stack frame stores:
o Parameters (arguments passed to the function),
o Local variables,
o Return address (where to continue execution after the function finishes).
 The stack grows with each recursive call until the base case is reached.
 Once the base case is met, the function starts returning values, and the stack unwinds
(frames are removed one by one).

Example: Factorial Function

The factorial of n is:

n!=n×(n−1)×(n−2)×…×1n! = n \times (n-1) \times (n-2) \times \ldots \times 1n!

=n×(n−1)×(n−2)×…×1

Recursive Definition:

 Base case: factorial(0) = 1

 Recursive case: factorial(n) = n * factorial(n-1)

Python code

int factorial(int n) {
if (n == 0) // base case
return 1;
else
return n * factorial(n - 1); // recursive case
}

Call Stack Example for factorial(3)

Function Calls:
factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))
=6
Call Stack Diagram:
Initial Call → factorial(3)
---------------------------------
| factorial(3) waiting result |
---------------------------------
| factorial(2) waiting result |
---------------------------------
| factorial(1) waiting result |
---------------------------------
| factorial(0) returns 1 (base) |

Stack unwinds ⬆️
---------------------------------

Return values:
factorial(0) = 1
factorial(1) = 1 * 1 = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6

Example : Fibonacci Function

int fibonacci(int n) {
if (n == 0) return 0; // Base case 1
if (n == 1) return 1; // Base case 2
return fibonacci(n-1) + fibonacci(n-2);
}
For fibonacci(4):

Call stack expands like this:

fibonacci(4)
= fibonacci(3) + fibonacci(2)
= (fibonacci(2) + fibonacci(1)) + (fibonacci(1) + fibonacci(0))

The stack will hold multiple active function calls until the base cases are reached, then values
return and combine.
Recursion vs Iteration

Definition

 Recursion: A function calls itself to solve a smaller instance of the same problem.
 Iteration: A set of instructions is repeatedly executed using loops (for, while, etc.).

Example Problem – Factorial of n

Recursive version (C):

int factorial(int n) {
if (n == 0) // base case
return 1;
else
return n * factorial(n - 1); // recursive case
}

Iterative version (C):

int factorial_iter(int n) {
int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

Recursion vs. Iteration

Recursion and iteration are two fundamental approaches to solving problems in programming.
While they can often achieve the same result, they differ in their implementation, efficiency, and
use cases.

1. Definition

 Recursion: A function calls itself to solve smaller instances of the same problem until a
base condition is met.
 Iteration: A loop (e.g., for, while) repeatedly executes a block of code until a condition
is satisfied.
2. Key Differences
Aspect Recursion Iteration

Uses loops to repeat a block of

Mechanism Function calls itself repeatedly.
code.

State Requires maintaining a call stack for each Does not require additional
Management function call. memory for state management.

Can be slower due to overhead of function Generally faster as it avoids

Performance
calls and stack usage. function call overhead.

Often more concise and easier to May require more lines of code for
Readability
understand for problems like tree traversal. complex problems.

Relies on a loop condition to

Termination Relies on a base case to stop recursion.
terminate.

Consumes more memory due to stack Memory-efficient as it uses a single

Memory Usage
frames. loop variable.

3. Example: Factorial Calculation

Using Recursion

Python
def factorial_recursive(n):
if n == 0 or n == 1: # Base case
return 1
return n * factorial_recursive(n - 1) # Recursive call

print(factorial_recursive(5)) # Output: 120

Using Iteration

Python
def factorial_iterative(n):
result = 1
for i in range(1, n + 1): # Loop from 1 to n
result *= i
return result

print(factorial_iterative(5)) # Output: 120

4. When to Use

 Recursion: Best suited for problems like tree/graph traversal, divide-and-conquer

algorithms (e.g., quicksort, mergesort), and mathematical problems like Fibonacci or
factorial.
 Iteration: Preferred for problems with simple repetitive tasks, such as traversing arrays
or performing cumulative calculations.

5. Summary

 Recursion is elegant and intuitive for problems with a natural recursive structure but can
be less efficient due to stack overhead.
 Iteration is more efficient and memory-friendly but may require more effort to implement
for complex problems.

Tail Recursion

Tail recursion is defined as a recursive function in which the recursive call is the last
statement that is executed by the function. So basically nothing is left to execute after the
recursion call.
Ex : Factorial Function

#include <stdio.h>

// Tail recursive helper function

int factorialHelper(int n, int acc) {

if (n == 0) {

return acc;

// The recursive call is the last operation (tail call)

return factorialHelper(n - 1, n * acc);

}
// Tail recursive factorial function

int factorial(int n) {

return factorialHelper(n, 1);

int main() {

int num = 5;

printf("Factorial of %d is %d\n", num, factorial(num));

return 0;

Difference between tail recursion and general recursion:

1. General Recursion

 In general recursion, the recursive call is not the last operation in the function.
 After the recursive call returns, some additional work might be done (like multiplying the
result, adding something, etc.).
 This means the function needs to keep information on the call stack to resume work after
each recursive call.

2. Tail Recursion

 In tail recursion, the recursive call is the last operation in the function.
 No additional work is done after the recursive call returns.
 This allows some compilers or interpreters to optimize the recursion by reusing the same
stack frame, making it as efficient as a loop.
 It usually involves passing an accumulator or extra parameters to carry the result forward.

Advantages of Tail Recursion

1. Optimized Memory Usage (Tail Call Optimization - TCO):

o Because the recursive call is the last operation, many compilers/interpreters can
optimize the function by reusing the current function’s stack frame instead of
creating a new one.
o This reduces the risk of stack overflow in deep recursion.
2. Improved Performance:
 o With tail call optimization, the recursion runs similarly to a loop, making it more
efficient in both time and space compared to general recursion.
3. Easier to Convert to Iterative Form:
o Tail recursive functions naturally resemble iterative loops because the recursive
call is the last operation.
o This makes it conceptually simpler to convert between recursion and iteration.
4. Cleaner Code for Some Problems:
o Tail recursion often leads to clearer and more maintainable code when dealing
with recursive algorithms, especially when accumulators or helper functions are
involved.
5. Better for Functional Programming:
o Many functional programming languages rely heavily on tail recursion and
optimize it extensively, allowing recursive algorithms without worrying about
stack overflows.

Tower of Hanoi Problem

Problem:
You have three pegs (let's name them A, B, and C) and n disks of different sizes stacked on peg
A in decreasing size order (largest at the bottom). The goal is to move all disks from peg A to
peg C, following these rules:

1. Only one disk can be moved at a time.

2. A disk can only be placed on an empty peg or on top of a larger disk.
3. You can use peg B as an auxiliary peg.

Recursive Solution

To move n disks from peg A to peg C using peg B as auxiliary:

1. Move the top (n-1) disks from A to B using C as auxiliary.

2. Move the nth (largest) disk from A to C directly.
3. Move the (n-1) disks from B to C using A as auxiliary.

This breaks the problem into smaller subproblems of size (n-1).

Deriving the Recurrence Relation

Let T(n) be the minimum number of moves required to transfer n disks.

 To move n disks:
o Move n−1 disks from A to B: T(n−1) moves.
o Move the largest disk from A to C: 1 move.
o Move n−1 disks from B to C: T(n−1) moves.
So,

T(n)=T(n−1)+1+T(n−1)=2T(n−1)+1

with the base case:

T(1)=1

Solving the Recurrence Relation

Given:

T(n)=2T(n−1)+1,T(1)=1T(n) = 2T(n-1) + 1, \quad T(1) = 1T(n)=2T(n−1)+1,T(1)=1

Let's expand it for the first few values:

T(1)=1T(2)=2T(1)+1=2×1+1=3T(3)=2T(2)+1=2×3+1=7T(4)=2T(3)+1=2×7+1=15\
begin{align*} T(1) &= 1 \\ T(2) &= 2T(1) + 1 = 2 \times 1 + 1 = 3 \\ T(3) &= 2T(2) + 1 = 2 \
times 3 + 1 = 7 \\ T(4) &= 2T(3) + 1 = 2 \times 7 + 1 = 15 \\ \end{align*}T(1)T(2)T(3)T(4)
=1=2T(1)+1=2×1+1=3=2T(2)+1=2×3+1=7=2T(3)+1=2×7+1=15

You can see a pattern:

T(n)=2n−1T(n) = 2^n - 1T(n)=2n−1

Recursive algorithm for computing the nth fibonacci number and the time complexity

#include <stdio.h>

int fibonacci(int n) {

if (n <= 1)

return n; // Base cases: fib(0) = 0, fib(1) = 1

return fibonacci(n - 1) + fibonacci(n - 2);

int main() {

int n = 10;

printf("Fibonacci number %d is %d\n", n, fibonacci(n));

 return 0;

Explanation

 The function fibonacci calls itself twice to calculate the two previous Fibonacci numbers.
 It stops when n=0n = 0n=0 or n=1n = 1n=1 (base cases).
 So the function builds a recursion tree where each call branches into two more calls,
except at the leaves.

Time Complexity

 The time complexity follows the recurrence:

T(n)=T(n−1)+T(n−2)+O(1)

 This is exactly the Fibonacci recurrence, which grows exponentially.

 Solution:

T(n)=O(2n)

because the number of function calls roughly doubles with each increase in nnn.

Recursive Function to Reverse a String

#include <stdio.h>

#include <string.h>

// Helper recursive function to reverse the string in place

void reverseString(char str[], int start, int end) {

if (start >= end) // Base case: pointers have met or crossed

return;

// Swap characters at start and end

char temp = str[start];

 str[start] = str[end];

str[end] = temp;

// Recursive call moving inward

reverseString(str, start + 1, end - 1);

int main() {

char str[] = "hello";

printf("Original string: %s\n", str);

reverseString(str, 0, strlen(str) - 1);

printf("Reversed string: %s\n", str);

return 0;

How the Recursion Stack Works During Execution

Let's say the input string is "hello".

 The function is called initially with start=0, end=4 (indices of 'h' and 'o').
 Step 1: Swap 'h' and 'o'. String becomes "oellh".
 Step 2: Recursive call with start=1, end=3 (swap 'e' and 'l').

Now the recursion stack looks like this:

reverseString("oellh", 0, 4)

-> calls reverseString("oellh", 1, 3)

-> calls reverseString("oellh", 2, 2)

 Step 3: Swap characters at indices 1 and 3: 'e' and 'l'. String becomes "olleh".
 Step 4: Recursive call with start=2, end=2.

At this point, start == end, which hits the base case:

  Function returns without further recursion because the middle of the string is reached.

Then, the stack unwinds, returning back through previous calls:

1. Return from reverseString("olleh", 2, 2) to reverseString("olleh", 1, 3).

2. Return from reverseString("olleh", 1, 3) to reverseString("olleh", 0, 4).
3. Return from reverseString("olleh", 0, 4) to main.

Recursive Algorithm to Compute Power of a number

We'll implement a classic approach called fast exponentiation or exponentiation by squaring,

which is more efficient than the naive recursion.

#include <stdio.h>

double power(double x, int n) {

if (n == 0)

return 1; // Base case: x^0 = 1

double temp = power(x, n / 2);

if (n % 2 == 0)

return temp * temp;

else if (n > 0)

return x * temp * temp;

else // For negative powers

return (temp * temp) / x;

int main() {

double x = 2.0;

int n = 10;

printf("%.2f^%d = %.2f\n", x, n, power(x, n));

return 0;
}

How it works:

 If n=0, return 1.
 Recursively compute power(x,⌊n/2⌋) and store it in temp.
 If n is even, xn=(xn/2)2=temp×temp
 If nnn is odd, xn=x * (x⌊n/2⌋)2=x×temp×temp
 Supports negative powers by returning reciprocal when n<0

Time Complexity Analysis:

 Each recursive call reduces nnn roughly by half: from n→n/2

 So the number of calls is proportional to the number of times you can divide nnn by 2
until it reaches 0.
 This is O(log n) time complexity.

Binary Tree
A Binary Tree Data Structure is a hierarchical data structure in which each node has at most
two children, referred to as the left child and the right child.

Different types of binary tree

 1. Full Binary Tree (or Proper Binary Tree):
 Definition: Every non-leaf node has exactly two children.
 Example:

/\

B C

/\

D E

In this example, A and B are non-leaf nodes, and both have two children.

2. Complete Binary Tree:

 Definition: All levels are completely filled except possibly the last level, and the last level is
filled from left to right.
 Example:

/\

B C

/\/

D EF

Here, all levels are full except the last, which is filled from left to right

3. Perfect Binary Tree:

 Definition: All internal nodes have exactly two children, and all leaf nodes are at the same level
(depth).
 Example:
A

/\

B C
 /\/\

D EF G

Every internal node has two children, and all leaves (D, E, F, G) are at the same depth.

4. Balanced Binary Tree:

 Definition: The height difference between the left and right subtrees of any node is at most
one. AVL trees and Red-Black trees are examples of self-balancing binary search trees.
 Example (AVL Tree):

/\

A C

The height difference between the left and right subtrees of B is 1 (height of left subtree = 1,
height of right subtree = 2).

5. Degenerate (or Pathological) Binary Tree:

 Definition: Each parent node has only one child, effectively making the tree resemble a linked
list.
 Example (Left-skewed):

Example (Right-skewed):

\
 B

Difference between binary tree and binary search tree

Feature Binary Tree Binary Search Tree (BST)

Ordering Nodes have no required order. Nodes are arranged in a specific order:
left child <is less than<parent <is less
than
<right child.
Structure A general data structure where each A specialized BST is always a binary
node can have at most two children. tree, but a binary tree is not always a
BST.
Operations Search, insertion, and deletion are Search, insertion, and deletion are
typically slower, with an average time faster, with an average time complexity
complexity of O(n)cap O open paren n of O(logn)cap O open paren log n close

𝑂(𝑛) 𝑂(log𝑛)
close paren paren

. for a balanced tree.

Duplicates Allows duplicate node values. Does not allow duplicate node values.
Use Cases Used for general tree structures and in Ideal for situations requiring fast
algorithms where ordering isn't a lookups, like database indexing, and
constraint. where efficient searching and sorting is
crucial.
 Array representation of a binary tree

The array representation of a binary tree, also known as sequential representation, stores the
nodes of the tree in a one-dimensional array. This representation is particularly effective for
complete or nearly complete binary trees. The nodes are typically stored level by level, from left
to right within each level, starting from the root.
Key Formulas (assuming 0-indexed array):
 Root Node: Stored at index 0.
 Left Child: For a node at index i, its left child is at index 2 * i + 1.
 Right Child: For a node at index i, its right child is at index 2 * i + 2.
 Parent Node: For a node at index i (where i > 0), its parent is at index (i - 1) / 2 (using integer
division, which effectively floors the result).

Example Tree and its Array Representation:

Consider a binary tree with nodes:
A

/\

B C

/\ \

D E F

The array representation of this tree would be:

['A', 'B', 'C', 'D', 'E', None, 'F']

Explanation of the Array Representation:

 A (Root): Stored at index 0.
 B (Left child of A): Stored at index 2 * 0 + 1 = 1.
 C (Right child of A): Stored at index 2 * 0 + 2 = 2.
 D (Left child of B): Stored at index 2 * 1 + 1 = 3.
 E (Right child of B): Stored at index 2 * 1 + 2 = 4.
 None (Left child of C): There is no left child for C, so a None or placeholder value is used at
index 2 * 2 + 1 = 5.
 F (Right child of C): Stored at index 2 * 2 + 2 = 6.
 Linked representation of a binary tree

The linked representation of a binary tree utilizes dynamically allocated nodes connected by
pointers to represent the hierarchical structure. Each node in this representation contains three
main components: a data field, a pointer to its left child, and a pointer to its right child.

Structure Definition:
A common C-style structure definition for a binary tree node is as follows:
struct Node {

int data; // Stores the value or data associated with the node

struct Node* left; // Pointer to the left child node

struct Node* right; // Pointer to the right child node

};

Explanation of Pointers:
 struct Node* left;:
This pointer stores the memory address of the node that serves as the current node's left child. If
a node does not have a left child, this pointer will typically be set to NULL.
 struct Node* right;:
Similar to the left pointer, this pointer stores the memory address of the node that serves as the
current node's right child. If a node does not have a right child, this pointer will also be set
to NULL.

Create a binary search tree for the following numbers start from an empty binary search
tree: 45,26,10,60,70,30,40. Delete keys 10,60 and 45 one after the other and show the trees
at each stage.

Initial Binary Search Tree

The initial binary search tree is created by inserting the numbers 45, 26, 10, 60, 70, 30, and 40 in
that order.
Step 1: Delete key 10
Key 10 is a leaf node (has no children). To delete a leaf node, simply remove it.

The tree after deleting 10:

Step 2: Delete key 60

Key 60 has one child (70). To delete a node with one child, replace the node with its child.

The tree after deleting 60:

 Step 3: Delete key 45
Key 45 is the root node and has two children. To delete a node with two children, replace it with
its in-order successor (the smallest value in its right subtree), which is 70. Then, delete the
original successor node. In this case, 70 had no children, so it is simply moved.

The tree after deleting 45:

Process of inserting and deleting a node in a Binary Search Tree

Inserting a node involves traversing the tree from the root, going left for smaller values and right
for larger ones, until an empty spot is found where the new node is added as a leaf. Deleting a
node depends on the number of children the node has: if it's a leaf, remove it; if it has one child,
replace it with that child; and if it has two children, replace its value with its in-order successor
or predecessor, then delete that successor/predecessor node.

Insertion process

1. Start at the root. If the tree is empty, the new node becomes the root.
2. Compare values. Compare the value of the new node with the current node's value.

3. Go left or right. If the new node's value is smaller, move to the left child. If it is larger, move to
the right child.

4. Repeat and insert. Continue this comparison and traversal until you find a null pointer,
indicating an empty spot. Create the new node and place it there.

Deletion process

Before deleting, you must first find the node to be removed. The subsequent action depends on
which of the three possible cases applies to the node.

Case 1: Deleting a leaf node (no children)

This is the simplest case.

 Action: Simply remove the node by setting the parent's pointer to null.

 Example:
o Before:

o 50
o / \
o 30 70
o / \
o 20 40
```
o Delete 20:
o 50
o / \
o 30 70
o \
o 40

Case 2: Deleting a node with one child

 Action: Replace the node to be deleted with its single child. The parent of the deleted node is
then updated to point to the child.

 Example:
o Before:
o 50
o / \
o 30 70
o \
o 40

o Delete 30:
o 50
o / \
o 40 70

Case 3: Deleting a node with two children

This is the most complex case, requiring a replacement for the deleted node that preserves the
BST property.

 Action:

 Find the in-order successor, which is the smallest node in the right subtree. This node has the
next greater value relative to the node being deleted.

 Copy the successor's value into the node you want to delete.

 Recursively delete the successor node from its original position. Since the successor will have at
most one child (a right child), this step can be handled by Case 1 or Case 2.

 Example:
o Before:

o 50
o / \
o 30 70
o / \/\

20 40 60 80
```
o Delete 50: The in-order successor is 60.

o Copy the value 60 into the node that holds 50.

o Delete the original node containing 60 (which is a leaf node).

o 60
o / \
o 30 70
/ \ \
 20 40 80

Given the preorder and inorder traversal of a binary tree, construct the binary tree.
Explain the steps involved.

Constructing a binary tree from its preorder and inorder traversals relies on the unique properties
of these traversals.
Steps Involved:
 Identify the Root:
The first element in the preorder traversal is always the root of the current subtree.
 Locate Root in Inorder:
Find the index of this root element within the inorder traversal. This index divides the inorder
traversal into two parts:
 Elements to the left of the root in the inorder traversal belong to the left subtree.
 Elements to the right of the root in the inorder traversal belong to the right subtree.
 Divide Preorder Traversal:
Based on the size of the left subtree (determined in step 2), divide the remaining part of the
preorder traversal:
 The next sequence of elements in the preorder traversal, corresponding to the size of the left
subtree, forms the preorder traversal of the left subtree.
 The remaining elements in the preorder traversal form the preorder traversal of the right subtree.
 Recursive Construction:
 Recursively call the construction process for the left subtree using its corresponding preorder and
inorder segments.
 Recursively call the construction process for the right subtree using its corresponding preorder
and inorder segments.
 Attach Subtrees:
Attach the constructed left subtree as the left child of the current root and the constructed right
subtree as the right child of the current root.
 Base Case:
The recursion terminates when either the preorder or inorder segment for a subtree becomes
empty, indicating an empty subtree (null node).
Example:
 Root is 3 (from preorder).
 In inorder, 3 is at index 1. Left subtree: [9], Right subtree: [15, 20, 7].
 Preorder for left subtree: [9]. Preorder for right subtree: [20, 15, 7].
 Recursively build left subtree: Root 9. Inorder [9]. Left/Right null.
 Recursively build right subtree: Root 20. Inorder [15, 20, 7]. Left subtree [15], Right subtree [7].
o Recursively build [15] and [7].
 Attach 9 as left child of 3. Attach 20 as right child of 3. Attach 15 as left child of 20. Attach 7 as
right child of 20.
This process continues until all subtrees are constructed and attached, forming the complete
binary tree.