Recursion: Given a stack, delete the middle element using recursion

Problem Statement:

You are given a stack, you need to delete the middle element using recursion.

Example:

Input:

s = {1, 2, 3, 4, 5}

Output:

s = {5, 4, 2, 1}

Solution Explanation:

Get the stack size, and a variable count to track current stack size.

Then recursively pop the element of the stack, then when the current count becomes equal to half of the stack, then pop the element.

Push the element that was popped before the recursive call.

Time Complexity: O(n)
Space Complexity: O(n)

Code Solution

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

void deleteMiddle(stack<int>& st, int sizeOfStack, int current)
{
    if(current == sizeOfStack / 2)
    {
        st.pop();
        return;
    }

    int x = st.top();
    st.pop();
    current += 1;

    deleteMiddle(st, sizeOfStack, current);
    st.push(x);
}


int main()
{
    stack<int> st;

    st.push(1);
    st.push(2);
    st.push(3);
    st.push(4);
    st.push(5);

    deleteMiddle(st, st.size(), 0);

    while (!st.empty())
    {
        int p = st.top();
        st.pop();
        cout << p << " ";
    }

    return 0;
}

Output

5 4 2 1