Reverse a stack in place using recursion

Problem

You are given a stack and you need to reverse it in place using recursion. You can only use the following Stack ADT functions:

push(x): Add an element x to the top of the stack.
pop(): Remove the element at the top of the stack.
peek(): Get the element at the top of the stack without removing it.
isEmpty(): Check whether the stack is empty.

The task is to reverse the stack such that the bottom-most element becomes the top-most, and the top-most element becomes the bottom-most, while using only the allowed stack operations and recursion.

Examples

Example 1:

1
2
3


Input: [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: The stack is reversed so that the bottom-most element (1) becomes the top-most element (5) and vice versa.

Example 2:

1
2
3


Input: [10, 20, 30]
Output: [30, 20, 10]
Explanation: The stack is reversed so that the bottom-most element (10) becomes the top-most element (30) and vice versa.

Example 3:

1
2
3


Input: []
Output: []
Explanation: An empty stack remains an empty stack when reversed.

Solution

Method 1 - Using Recursion

To reverse a stack in place using recursion, the key is to use an auxiliary recursive function to recursively pop elements from the stack until the stack is empty, and then use another recursive helper function to insert the elements at the bottom of the stack instead of the top. This ensures that the order of elements gets reversed.

Approach

Reverse Function: This function uses recursion to pop all elements until the stack becomes empty. For each element popped, we call the Insert at Bottom function to insert the element at the bottom of the stack.
Insert at Bottom Function: This auxiliary function ensures that given an element x, it recursively pops elements until the stack becomes empty, then pushes x, and subsequently pushes all elements back in the order they were popped.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


public class Solution {

    public void reverse(Stack<Integer> stack) {
        if (stack.isEmpty()) {
            return;
        }
        int top = stack.pop();
        reverse(stack);
        insertAtBottom(stack, top);
    }

    private void insertAtBottom(Stack<Integer> stack, int value) {
        if (stack.isEmpty()) {
            stack.push(value);
            return;
        }
        int top = stack.pop();
        insertAtBottom(stack, value);
        stack.push(top);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def reverse(self, stack: List[Any]) -> None:
        if not stack:
            return
        top = stack.pop()
        self.reverse(stack)
        self.insert_at_bottom(stack, top)

    def insert_at_bottom(self, stack: List[Any], value: Any) -> None:
        if not stack:
            stack.append(value)
            return
        top = stack.pop()
        self.insert_at_bottom(stack, value)
        stack.append(top)

Complexity

⏰ Time complexity: O(n^2) as each call to reverse causes a sequence of insertions which can take O(n) steps due to recursive inserts, with n stack elements causing total complexity of O(n^2).
🧺 Space complexity: O(n), as the space used by the call stack due to recursion will be at most the depth of the recursion, which is O(n) for n elements in the stack.

Problem#

Examples#

Solution#

Method 1 - Using Recursion#

Approach#

Code#

Complexity#