Answer 1

Algorithm to Check for a Loop in a Singly Linked List

1. Initialize Two Pointers:
 Initialize two pointers: slow and fast.
 Set both pointers to the head of the linked list.
2. Move Pointers:
 Move the slow pointer one step at a time and the fast pointer two steps at a time.
 Continue this process until either the fast pointer reaches the end of the list (indicating no loop) or
the slow and fast pointers meet (indicating a loop).
3. Check for Loop:
 If the fast pointer reaches the end of the list (i.e., becomes NULL), return false (indicating no loop).
 If the slow and fast pointers meet (i.e., they point to the same node), return true (indicating a loop).

Dry Run Example

Consider the following singly linked list with a loop:
1 -> 2 -> 3 -> 4 -> 5 -> 6
^ |
| v
9 <- 8 <- 7 <- 11

Step 1: Initialize Pointers

 slow pointer: 1 (head)
 fast pointer: 1 (head)
Step 2: Move Pointers
 Iteration 1:
 slow pointer: 2
 fast pointer: 3
 Iteration 2:
 slow pointer: 3
 fast pointer: 5
 Iteration 3:
 slow pointer: 4
 fast pointer: 7
 Iteration 4:
 slow pointer: 5
 fast pointer: 9
 Iteration 5:
 slow pointer: 6
 fast pointer: 11
Step 3: Check for Loop
Since the fast pointer has reached the end of the list (NULL), we conclude that there is no loop in the linked list.

This algorithm has a time complexity of 𝑂(𝑛) and requires only constant space, making it suitable for practical use.
 Answer 2

To design a SpecialStack that supports push(), pop(), isEmpty(), top(), and getMin() operations in O(1) time
complexity, we can use two stacks:
 One main stack to store the actual stack elements.
 One auxiliary stack to store the minimum values.

Design Explanation
 Main Stack (mainStack): This stack stores the actual stack elements.
 Auxiliary Stack (minStack): This stack keeps track of the minimum element at each level of the stack.
Whenever we push a new element onto the mainStack, we also push the minimum of the new element and the
current minimum onto the minStack.

Operations
1. push(x):
Push x onto the mainStack.
Push the minimum of x and the current top of minStack onto minStack.

2. pop():
Pop the top element from mainStack.
Pop the top element from minStack.

3. isEmpty():
Return True if mainStack is empty; otherwise, return False.

4. top():
Return the top element of mainStack.

5. getMin():
Return the top element of minStack.

Dry Run/Step-by-Step Execution

1. push(3):
mainStack: [3]
minStack: [3]
2. push(5):
mainStack: [3, 5]
minStack: [3, 3] (3 is still the minimum)
3. getMin():
Output: 3 (top of minStack)
4. push(2):
mainStack: [3, 5, 2]
minStack: [3, 3, 2] (2 is the new minimum)
5. push(1):
mainStack: [3, 5, 2, 1]
minStack: [3, 3, 2, 1] (1 is the new minimum)
6. getMin():
Output: 1 (top of minStack)
7. pop():
mainStack: [3, 5, 2]
minStack: [3, 3, 2]
 8. getMin():
Output: 2 (top of minStack)
9. pop():
mainStack: [3, 5]
minStack: [3, 3]
10. top():
Output: 5 (top of mainStack)
11. isEmpty():
Output: False (since mainStack is not empty)

Final State of Stacks

mainStack: [3, 5]
minStack: [3, 3]

This design ensures that each operation runs in O(1) time complexity.
 Answer 3

To merge two binary search trees 𝑇1 and 𝑇2 into a balanced binary search tree in linear time, we can follow these
steps:
Algorithm for Merging Two Binary Search Trees into a Balanced Binary Search Tree

 Perform in-order traversals of both 𝑇1 and 𝑇2 to obtain two sorted lists of elements.
1. Perform In-order Traversals:

2. Merge Sorted Lists:

 Merge the two sorted lists obtained from the in-order traversals into one sorted list.
3. Construct Balanced Binary Search Tree:
 Construct a balanced binary search tree from the merged sorted list.

Dry Run Example

Tree 𝑇1:
Consider the following two binary search trees:

5
/\
3 8
/\ \
2 4 10
/ /
1 9

Tree 𝑇2:
6
/\
3 9
/\ \
1 4 11

In-order Traversal of 𝑇1: 1, 2, 3, 4, 5, 8, 9, 10

Step 1: In-order Traversals

In-order Traversal of 𝑇2: 1, 3, 4, 6, 9, 11

Step 2: Merge Sorted Lists
Merge the two sorted lists obtained from the in-order traversals:
Merged Sorted List: 1, 1, 2, 3, 3, 4, 4, 5, 6, 8, 9, 9, 10, 11
Step 3: Construct Balanced Binary Search Tree
Construct a balanced binary search tree from the merged sorted list:
5
/ \
3 9
/\ /\
2 4 6 10
/ \ \
1 8 11

Summary
This algorithm runs in linear time because the in-order traversal and list merging steps take linear time, and
constructing a balanced binary search tree from a sorted list also takes linear time. Therefore, the overall time
complexity of the algorithm is linear.
 Answer 4

To prove that the total cost of 𝑛 operations (PUSH, POP, or MULTIPOP) on an initially empty stack is 𝜃(𝑛).

Each element pushed onto the stack is eventually popped off by either a POP or a MULTIPOP operation. Hence, the
number of POP or MULTIPOP operations cannot exceed the number of PUSH operations.

Proof by Amortized Analysis

1. PUSH operations:
 Each PUSH costs 1.
 For m PUSH operations, the total cost is m.
2. POP operations:
 Each POP costs 1.
 Since every pushed element must be popped, the number of POP operations p is at most m.
 The total cost for POP operations is p, where p≤m.

3. MULTIPOP operations:
 Each MULTIPOP operation has a cost of k, where k is the number of elements to pop.
 For q MULTIPOP operations, each removing ki elements, the total cost is the sum of all ki values.
 The total number of elements popped by MULTIPOP operations cannot exceed the total number of
PUSH operations. Hence, the sum of all ki values is at most m.

Total Cost Calculation

 Total cost for PUSH operations: 𝑚.

Combining the costs of all operations:

 Total cost for POP operations: 𝑝, where 𝑝≤𝑚.

Therefore, the total cost 𝑇(𝑛) of all operations is:

 Total cost for MULTIPOP operations: ∑ ki ≤𝑚.

𝑇(𝑛)=𝑚+𝑝+∑ ki
Since 𝑝≤𝑚 and ∑ ki ≤𝑚, we have:
𝑇(𝑛)≤𝑚+𝑚+𝑚=3𝑚

Given that the number of PUSH operations 𝑚 is at most 𝑛, we have: 𝑇(𝑛)≤3𝑛

Thus, the total cost 𝑇(𝑛) is 𝑂(𝑛). Since each operation has a non-zero cost, the total cost is also Ω(𝑛). Combining
these results, we conclude: 𝑇(𝑛)=𝜃(𝑛)
 Answer 5

Algorithm to Find the kth Node in In-order Traversal

1. Initialize:
 Use a stack to perform iterative in-order traversal.
 Use a counter to keep track of the number of nodes visited.
2. In-order Traversal:
 Start from the root and push all left children onto the stack until reaching a leaf.

 If the counter equals 𝑘, return the node's value.

 Pop the stack and process the node, increment the counter.

 Move to the right child of the node and continue the process.

Dry Run Example

Consider the following binary tree:
5
/\
3 8
/\ \
2 4 10
/ /
1 9
Let's find the 4th node in in-order traversal.

Detailed Algorithm Steps

1. Initialization:
 Stack: []
 Counter: 0
 Current Node: 5 (root)
2. In-order Traversal:
 Step 1: Push left children of 5
 Stack: [5, 3, 2, 1]
 Current Node: None (1 has no left child)

 Step 2: Pop from stack and process node 1

 Stack: [5, 3, 2]
 Current Node: 1
 Counter: 1
 Move to the right child of 1 (None)

 Step 3: Pop from stack and process node 2

 Stack: [5, 3]
 Current Node: 2
 Counter: 2
 Move to the right child of 2 (None)

 Step 4: Pop from stack and process node 3

 Stack: [5]
 Current Node: 3
 Counter: 3
 Move to the right child of 3 (4)
  Step 5: Push left children of 4
 Stack: [5, 4]
 Current Node: None (4 has no left child)

 Step 6: Pop from stack and process node 4

 Stack: [5]
 Current Node: 4
 Counter: 4 (Counter equals k)

The 4th node in the in-order traversal is node 4.

Summary
An iterative in-order traversal with a stack and counter can efficiently find the kth node in O(n) time in the worst case,
where n is the number of nodes. This approach ensures each node is traversed once, making it optimal. It works for
both binary trees and binary search trees (BSTs), and for BSTs, it visits nodes in ascending order.
 Answer 6

Algorithm to Find the Successor and Predecessor in a Binary Tree

1. In-order Traversal:
o Perform an in-order traversal of the binary tree.
o While traversing, keep track of the previous node visited.
2. Identify Successor and Predecessor:
o During the traversal, check if the current node matches the target node.
o If it does, the previous node is the predecessor, and the next node visited will be the successor.

Dry Run Example

Consider the following binary tree:
15
/ \
10 20
/ \ / \
8 12 17 25
/ \ \
6 16 27

Step-by-Step Dry Run

1. Initialize:
o Current node: 15 (root)
o Previous node: None
o Successor: None
o Predecessor: None
2. In-order Traversal:
o Traverse left subtree of 15 (node 10).
3. Visit Node 10:
o Traverse left subtree of 10 (node 8).
o Visit Node 8:
 Traverse left subtree of 8 (node 6).
 Visit Node 6:
 Traverse left subtree of 6 (None).
 Process node 6:
 Previous node: 6
 Traverse right subtree of 6 (None).
 Process node 8:
 Previous node: 8
 Set predecessor of 10 to 8 (previous node before visiting 10).
 Traverse right subtree of 8 (None).
o Process node 10:
 Previous node: 10
o Traverse right subtree of 10 (node 12).
4. Visit Node 12:
o Traverse left subtree of 12 (None).
o Process node 12:
 Set successor of 10 to 12 (next node after visiting 10).
 Previous node: 12
o Traverse right subtree of 12 (None).
5. Complete In-order Traversal:
o Continue traversal to process the rest of the tree (nodes 15, 20, 17, 16, 25, and 27).
Summary

After the in-order traversal:

 Predecessor of 10: 8 (the last node visited before 10).

 Successor of 10: 12 (the first node visited after 10).

This method runs in O(n) time, where n is the number of nodes in the binary tree.
 Answer 7

The goal of this algorithm is to rearrange the elements in the given list such that all non-empty elements (A, B, C, D,
E, F, G) are moved to the end of the list, while the empty slots (_) are moved to the beginning.

Steps
1. Initialization:
o n = length of arr assigns the length of the array to n.
o write = n - 1 initializes the write pointer to the last index of the array.
2. Single Loop Traversal:
o The loop runs from the last index to the first index (i from n - 1 to 0).
o Within the loop, if arr[i] is a non-empty element, it is written to the position write and write is
decremented.
3. Filling Remaining Positions with Empty Slots:
o After the loop, the write pointer indicates the last position filled with a non-empty element.
o A second loop runs from the start of the array to the current position of write (inclusive) and fills
these positions with _.

Algorithm (Pseudo Code):

function collapse(arr):
n = length of arr
write = n - 1

// Traverse from end to beginning

for i from n - 1 down to 0:
if arr[i] is not '_':
arr[write] = arr[i]
write -= 1

// Fill remaining positions with '_'

for i from 0 to write:
arr[i] = '_'

Time Complexity:
The algorithm uses a single traversal of the array and a subsequent traversal up to write, both of which are O(n).
Therefore, the overall time complexity is O(n).

Space Complexity:
The algorithm uses only a constant amount of extra space (the write pointer), so the space complexity is O(1).
 Answer 8

The goal of this algorithm is to rearrange the elements in the given list such that all non-empty elements (A, B, C, D,
E, F, G) are moved to the beginning of the list, while the empty slots (_) are moved to the end.

Steps
1. Initialization:
o n = length of arr assigns the length of the array to n.
o write = 0 initializes the write pointer to the first index of the array.
2. Single Loop Traversal:
o The loop runs from the first index to the last index (i from 0 to n - 1).
o Within the loop, if arr[i] is a non-empty element, it is written to the position write and write is
incremented.
3. Filling Remaining Positions with Empty Slots:
o After the loop, the write pointer indicates the first position to be filled with _.
o A second loop runs from the current position of write to the end of the array and fills these positions
with _.

Algorithm (Pseudo Code):

function collapse(arr):
n = length of arr
write = 0

// Traverse from beginning to end

for i from 0 to n - 1:
if arr[i] is not '_':
arr[write] = arr[i]
write += 1

// Fill remaining positions with '_'

for i from write to n - 1:
arr[i] = '_'

Time Complexity:
The algorithm uses a single traversal of the array and a subsequent traversal from write to the end, both of which are
O(n). Therefore, the overall time complexity is O(n).

Space Complexity:9
The algorithm uses only a constant amount of extra space (the write pointer), so the space complexity is O(1).
 Answer 9

Steps of the Algorithm

1. Initialize:
 A queue to perform the BFS traversal.
 A dictionary or array to store the depths of each node.
2. Start BFS from the root:
 Enqueue the root node and set its depth to 0.
3. Process the Queue:
 While the queue is not empty:
 Dequeue a node.
 For each child of the dequeued node:
 Set the depth of the child to be the depth of the current node plus 1.
 Enqueue the child.

Consider the following tree 𝑇

Dry Run Example

A
/|\
B C D
/\ /\
E F G H
\
I

Initial Setup
 Queue: [A]
 Depth Dictionary: {A: 0}

Steps
1. Process Node A:
 Dequeue A.
 Enqueue its children B, C, and D.
 Set their depths:
 Depth(B) = Depth(A) + 1 = 1
 Depth(C) = Depth(A) + 1 = 1
 Depth(D) = Depth(A) + 1 = 1
 Queue: [B, C, D]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1}
2. Process Node B:
 Dequeue B.
 Enqueue its children E and F.
 Set their depths:
 Depth(E) = Depth(B) + 1 = 2
 Depth(F) = Depth(B) + 1 = 2
 Queue: [C, D, E, F]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2}
3. Process Node C:
 Dequeue C (C has no children).
 Queue: [D, E, F]
  Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2}

4. Process Node D:
 Dequeue D.
 Enqueue its children G and H.
 Set their depths:
 Depth(G) = Depth(D) + 1 = 2
 Depth(H) = Depth(D) + 1 = 2
 Queue: [E, F, G, H]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2}
5. Process Node E:
 Dequeue E (E has no children).
 Queue: [F, G, H]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2}
6. Process Node F:
 Dequeue F (F has no children).
 Queue: [G, H]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2}
7. Process Node G:
 Dequeue G.
 Enqueue its child I.
 Set depth of I:
 Depth(I) = Depth(G) + 1 = 3
 Queue: [H, I]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3}
8. Process Node H:
 Dequeue H (H has no children).
 Queue: [I]
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3}
9. Process Node I:
 Dequeue I (I has no children).
 Queue: []
 Depth Dictionary: {A: 0, B: 1, C: 1, D: 1, E: 2, F: 2, G: 2, H: 2, I: 3}

Final Depths
 A: 0
 B: 1
 C: 1
 D: 1
 E: 2
 F: 2
 G: 2
 H: 2
 I: 3

By using BFS, we ensure that each node is visited exactly once and its depth is computed in 𝑂(1) time. Hence, the
Summary

total time complexity of computing the depths of all nodes in the tree 𝑇 is 𝑂(𝑛), where 𝑛 is the number of nodes in
the tree.
 Answer 10

To search for an arbitrary element in a max heap, we need to check whether the element exists in the heap or not.
The heap structure ensures that every parent node is greater than or equal to its children (in the case of a max heap).

Steps:
1. Start from the root of the heap.
2. If the current node matches the element, return True.
3. If the current node is greater than the element, recursively search in its children.
4. If the current node is less than the element, stop searching that branch (as all descendants will also be
smaller).
5. If we exhaust all nodes without finding the element, return False.

Dry Run Example

Consider the following max heap:
100
/ \
90 80
/\ /\
70 60 50 40
/\ /
35 30 20

Let's search for the element 50.

Detailed Algorithm
1. Start at the root (100).
2. 50 < 100, so we search both children.
3. Move to the left child (90).
 50 < 90, so we search both children.
4. Move to the left child (70).
 50 < 70, so we search both children.
5. Move to the left child (35).
 50 > 35, stop searching this branch.
6. Move to the right child (30).
 50 > 30, stop searching this branch.
7. Move back to 90, now check its right child (60).
 50 < 60, so we search both children.
8. Move to the left child (20).
 50 > 20, stop searching this branch.
9. Move back to the root, now check its right child (80).
 50 < 80, so we search both children.
10. Move to the left child (50).
 50 == 50, element found.

Conclusion
The element 50 is found in the heap.
Dry Run for Searching an Element Not in the Heap
Let's search for the element 85.
1. Start at the root (100).
2. 85 < 100, so we search both children.
3. Move to the left child (90).
 85 < 90, so we search both children.
4. Move to the left child (70).
 85 > 70, stop searching this branch.
5. Move to the right child (60).
 85 > 60, stop searching this branch.
6. Move back to 90, now check its right child (60).
 85 > 60, stop searching this branch.
7. Move back to the root, now check its right child (80).
 85 > 80, stop searching this branch.

Conclusion
The element 85 is not found in the heap.

The worst-case time complexity of the search operation in a heap is 𝑂(𝑛), as in the worst case, we may need to visit
Algorithm Efficiency

all nodes. However, the heap property allows us to prune branches effectively, potentially reducing the number of
comparisons needed.