270. Insert an Element at the Bottom of a Stack

Given a stack of n integers (given as space-separated values from bottom to top) and a value x, insert x at the very bottom of the stack - beneath every existing element - using only recursive stack operations (push/pop/peek/isEmpty, no other data structure). Print the resulting stack's values from top to bottom.

Input: The first line contains n space-separated integers, the stack's values from bottom to top. The second line contains x, the value to insert at the bottom. Output: Print the resulting stack's values, space-separated, from top to bottom.

1 <= n <= 10^4

This exact 'recursively empty the stack, then rebuild on the way back up' technique is the foundational building block for 'Reverse a Stack Using Recursion' and 'Sort a Stack Using Recursion' - mastering it here makes both of those noticeably easier.

Add a new value beneath every existing element in a stack, using only stack operations (no other data structure). Brute force: Copy the stack's contents into an array, prepend the new value, and rebuild the stack from that array - this works but uses an explicit auxiliary array, which the problem specifically disallows (only push/pop/peek/isEmpty are permitted). Optimised: Using the RECURSION CALL STACK itself as the only 'extra storage' (rather than an explicit auxiliary array) satisfies the problem's constraint - each recursive call holds exactly one popped value in its own local variable, and the call stack's own LIFO unwinding naturally restores everything in the correct order.

Pop every element off the original stack one at a time and push each one onto a separate, second stack, which reverses their order. Once the original stack is empty, push x onto it, and then pop everything off the auxiliary stack back onto the original, restoring the original order with x now underneath everything. This clearly achieves the goal, but it relies on an explicit second stack as scratch space, which doesn't satisfy the stricter requirement of solving this using recursion and the call stack alone (no other data structure). Time: O(n) Space: O(n)

Write a recursive function that pops the top element, recurses on the (now smaller) stack, and along the way appends each popped value to a plain array/list as the recursion unwinds; once the base case (empty stack) is hit, push x. Afterward, push the array's contents back onto the stack in the correct order. This uses recursion to walk down to the bottom of the stack, but it still leans on an auxiliary array to hold the popped values during the unwind, rather than relying purely on the function call stack to hold that state. Time: O(n) Space: O(n)

Write a single recursive function insertAtBottom(stack, x): if the stack is empty, just push x and return; otherwise, pop the top element into a local variable, recursively call insertAtBottom(stack, x) on the remaining stack, and once that call returns, push the saved local value back on top. Every popped value lives only in that call's local variable on the call stack itself - no separate array or second stack is ever created, fully satisfying the 'recursion and stack operations only' requirement. This is the standard, minimal solution: one pass down to insert x at the true bottom, and one pass back up restoring every element, using only the implicit memory of the recursion. Time: O(n) Space: O(n) (recursion stack)

1. Recursively pop every element off the stack, one at a time, until it's completely empty. 2. Once empty, push the new value x - it's now the only element, sitting at the bottom. 3. As the recursion unwinds (returns), push each previously-popped element back on, in the reverse order they were removed - restoring the original stack exactly, but now with x underneath everything.

Time: O(n) - each element is popped once and pushed back once. Space: O(n) for the recursion call stack (holding one value per call) - this counts as the 'allowed' extra space here, since only OTHER explicit data structures are disallowed.

n = 1 (inserting x beneath a single existing element); n = 10^4, the upper bound, given that only recursive stack operations are allowed; the output order (top to bottom) is the reverse of the input order (bottom to top), so x always appears last.

Be ready to explain clearly WHY using recursion satisfies the 'no other data structure' constraint - the call stack itself is doing the job an explicit auxiliary stack normally would, just implicitly via function calls.