Problem Statement

Given a stack of integers, your task is to delete the middle element of the stack using recursion. You are not allowed to use any additional data structures like arrays or queues. Only stack operations (push, pop, isEmpty, etc.) can be used.

Middle Element Definition: If the stack has a odd number of element, the middle element is the one at position size / 2 + 1 (1-based index). If the stack has an even number of element, remove the lower middle element.

Examples

Example 1:

Input:
    |  1  | <- Top
    |  2  |
    |  3  |
    |  4  |
    |  5  |
    +-----+

Output:
    |  1  | <- Top
    |  2  |
    |  4  |
    |  5  |
    +-----+

Explanation:
The middle element is 3 (position 3 in 1-based indexing)

Example 2:

Input:
    |  1  | <- Top
    |  2  |
    |  3  |
    |  4  |
    +-----+

Output:
    |  1  | <- Top
    |  4  |
    |  5  |
    +-----+

Explanation:
The stack has an even number of elements, so the middle is at position 2, which is 2.

Different Approaches

1️⃣ Recursion

Intuition:

To delete the middle element of a stack, we can leverage recursion to simulate an iterative process:

1. We can recursively remove elements from the stack until we reach the middle element.
2. Once we reach the middle element, we simply skip it (i.e., we don’t push it back to the stack).
3. During backtracking (as each recursive call completes), we push the previously removed elements back into the stack.

This recursive approach lets us avoid needing additional data structures, as each recursive call effectively acts as temporary storage for the removed elements.

Approach

1. Define a recursive function deleteMiddleHelper that:
   • Takes the current stack, the size of the stack, and a currentIndex parameter that helps us track when we’ve reached the middle element.
2. In the deleteMiddleHelper function:
   • Base case: If the current index matches the middle index, pop the middle element and return.
   • Otherwise, pop the top element and recursively call deleteMiddleHelper on the remaining stack with currentIndex + 1.
   • After the recursive call completes (backtracking phase), push the popped element back onto the stack.
3. In the main deleteMiddle function:
   • Calculate the middle index of the stack (size / 2 for 0-based indexing).
   • Call deleteMiddleHelper with the calculated middle index.

Dry Run:

Initialization:

stack = |  1  |
        |  2  |
        |  3  |
        |  4  |
        |  5  |
        +-----+

size = 5
Middle Index = 5 / 2 = 2, so the middle element is 3 (0-based index).

First Iteration:

Current Index = 0
Pop Top which is 1

Second Iteration:

Current Index = 1
Pop Top which is 2

Third Iteration:

Current Index = 2
Pop Top which is 3, This is middle element, do not push back

Code:

#include <iostream>
#include <stack>
using namespace std;

// Recursive helper function to delete the middle element
void deleteMiddleHelper(stack<int>& s, int currentIndex, int middleIndex) {
    // Base case: if we have reached the middle index
    if (currentIndex == middleIndex) {
        s.pop(); // Remove the middle element
        return;
    }

    // Pop the top element and store it temporarily
    int topElement = s.top();
    s.pop();

    // Recursive call to continue moving towards the middle
    deleteMiddleHelper(s, currentIndex + 1, middleIndex);

    // Push the element back after the middle element is deleted
    s.push(topElement);
}

// Function to delete the middle element of a stack
void deleteMiddle(stack<int>& s, int size) {
    // If stack is empty or has only one element, there's no middle to delete
    if (size == 0) return;

    int middleIndex = size / 2; // Middle index for 0-based indexing
    deleteMiddleHelper(s, 0, middleIndex);
}

// Helper function to print stack
void printStack(stack<int> s) {
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

int main() {
    stack<int> s;
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    cout << "Original Stack:" << endl;
    printStack(s);

    // Re-create stack for printing after function call
    s.push(1);
    s.push(2);
    s.push(3);
    s.push(4);
    s.push(5);

    // Delete middle element
    deleteMiddle(s, 5);

    cout << "Stack after deleting middle element:" << endl;
    printStack(s);

    return 0;
}