AlgoViz
HomeRecursion

Reverse a Stack

Medium

Insert each element at the bottom

Problem

Reverse a stack using only recursion.

In simple words

Pull everything out, then push each back at the very bottom.

The idea

Pop the top, reverse the remainder, then push the saved element all the way to the bottom using a helper that recurses until the stack is empty. Again the call stack is the only extra storage.

The trick

  • insertAtBottom recurses until empty, pushes, then unwinds.
  • O(n²) time, O(n) stack.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
0
1
2

Step 1 of 2. Here's the example — bottom [1,2,3] top Values: 1, 2, 3.

1/2
Optimal
timeO(n^2)spaceO(n)
1reverse(st):2  if empty: return3  x = pop()4  reverse(st)5  insertAtBottom(st, x)

Input

array
[1, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
bottom [1,2,3] top
Output:
bottom [3,2,1] top

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.