Introduction

Stack-based problems are a core part of data structures and algorithms (DSA) interviews. One such interesting and frequently asked question is deleting the middle element of a stack without using any additional data structure.

At first glance, this problem may seem tricky because stacks only allow access to the top element. However, with the help of recursion, it becomes an elegant and intuitive solution.

In this article, we will break down the problem, build the intuition, and implement an efficient recursive approach step by step.

Link of Problem: GeeksforGeeks – Delete Middle of a Stack

Problem Statement

Given a stack s, delete the middle element of the stack without using any additional data structure.

Definition of Middle Element

The middle element is defined as:

1. Indexing starts from the bottom of the stack (1-based indexing)

Examples

Example 1

Input:

s = [10, 20, 30, 40, 50]

Output:

[50, 40, 20, 10]

Explanation:

1. Middle index = (5+1)/2 = 3
2. Middle element = 30 → removed

Example 2

Input:

s = [10, 20, 30, 40]

Output:

[40, 30, 10]

Explanation:

1. Middle index = (4+1)/2 = 2
2. Middle element = 20 → removed

Key Insight

Stacks follow LIFO (Last In, First Out), meaning:

1. You can only access/remove the top element
2. You cannot directly access the middle

So how do we solve it?

We use recursion to:

1. Pop elements until we reach the middle
2. Remove the middle element
3. Push back all other elements

This way, no extra data structure is used—just the recursion call stack.

Approach: Recursive Solution

Idea

1. Calculate the middle position
2. Recursively remove elements from the top
3. When the middle is reached → delete it
4. While returning, push elements back

Code (Java)

Step-by-Step Dry Run

Let’s take:

1. Middle index = 3
2. Recursion pops: 50 → 40
3. Now stack size = 3 → remove 30
4. Push back: 40 → 50

Final Stack:

[10, 20, 40, 50]

Complexity Analysis

1. Time Complexity: O(n)
2. Each element is removed and added once
3. Auxiliary Space: O(n)
4. Due to recursion call stack

Why This Approach Works

1. Recursion simulates stack behavior
2. No extra data structures like arrays or lists are used
3. Maintains original order after deletion
4. Efficient and interview-friendly solution

Key Takeaways

1. Direct access to middle is not possible in a stack
2. Recursion is the key to solving such constraints
3. Always think of breaking + rebuilding for stack problems
4. This pattern is useful in many stack-based interview questions

When This Problem Is Asked

This problem is commonly seen in:

1. Technical interviews
2. Coding platforms like GeeksforGeeks
3. Stack and recursion-based problem sets

It evaluates:

1. Understanding of stack operations
2. Recursive thinking
3. Problem-solving under constraints

Conclusion

Deleting the middle element of a stack without extra space is a classic example of using recursion effectively. While the problem may seem restrictive, the recursive approach provides a clean and optimal solution.

Mastering this concept will help you tackle more advanced stack and recursion problems with confidence.

Frequently Asked Questions (FAQs)

1. Can this be solved without recursion?

Not efficiently without using another data structure. Recursion is the best approach under given constraints.

2. Why not use an array or list?

The problem explicitly restricts the use of additional data structures.

3. What is the best approach?

The recursive approach is optimal with O(n) time and space complexity.