Insert an element at the bottom of a stack using recursion

Easy

Problem

Push x to the bottom of a stack using only push, pop and recursion — no other data structure.

Example 1

Input:  stack (bottom → top) [1, 2, 3], x = 0
Output: [0, 1, 2, 3]

Also asked as: Implement a method to insert an element at its bottom without using any other data structure

Test cases

Case 1

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

Case 2

Input:    [7], 1
Expected: [1,7]

Case 3

Input:    [], 5
Expected: [5]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Recursively pop to the bottom, place, unwind

Time O(n)Space O(n) call stack

If the stack is empty, push x. Otherwise pop the top, recurse, then push the top back.

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