Reverse a stack using recursion

Easy

Problem

Reverse a stack using only its push and pop operations and recursion — no extra array or stack.

Example 1

Input:  (bottom → top) [1, 2, 3, 4]
Output: [4, 3, 2, 1]

Also asked as: Reverse a stack using recursion

Test cases

Case 1

Input:    [1,2,3,4]
Expected: [4,3,2,1]

Case 2

Input:    [1,2]
Expected: [2,1]

Case 3

Input:    [1]
Expected: [1]

Case 4

Input:    []
Expected: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Pop all, then insert each at the bottom

Time O(n²)Space O(n)

Recursively empty the stack; as the recursion unwinds, insert each popped value at the bottom.

function reverseStack(stack) {
if (stack.length === 0) return;
const top = stack.pop();
reverseStack(stack);
insertAtBottom(stack, top);
}
function insertAtBottom(stack, x) {
if (!stack.length) { stack.push(x); return; }
const t = stack.pop();
insertAtBottom(stack, x);
stack.push(t);
}