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

Problem Statement

Given a stack, insert an element at the bottom of the stack without using any other data structure. You can only use the stack itself and recursion.

Example:

Approach 1: Using Recursion (Standard)

Intuition

Use the call stack as implicit storage. Pop all elements recursively, insert the new element when the stack is empty, then push all elements back.

Algorithm

1. Base case: if stack is empty, push the element
2. Recursive case: pop top element, recursively insert at bottom, push the popped element back

import java.util.*;

public class InsertAtBottom {
    public static void insertAtBottom(Stack<Integer> stack, int x) {
        // Base case: stack is empty, push the element
        if (stack.isEmpty()) {
            stack.push(x);
            return;
        }
        
        // Recursive case: pop top, insert at bottom, push back
        int top = stack.pop();
        insertAtBottom(stack, x);
        stack.push(top);
    }
    
    public static void printStack(Stack<Integer> stack) {
        System.out.println("Stack (bottom to top): " + stack);
    }
    
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
        stack.push(4);
        
        System.out.println("Before insertion:");
        printStack(stack);
        
        insertAtBottom(stack, 0);
        
        System.out.println("After inserting 0 at bottom:");
        printStack(stack);
    }
}

Complexity Analysis

• Time Complexity: O(n) - we process each element once
• Space Complexity: O(n) - recursion stack holds all n elements

How Recursion Works

Let's trace through the example:

Variation: Insert at Kth Position from Bottom

Variation: Insert in Sorted Stack

Key Takeaways

1. Recursion uses call stack as implicit storage, satisfying the "no other data structure" constraint
2. The pattern: pop all → do something at base → push all back
3. This is a fundamental technique used in:
   • Reversing a stack
   • Sorting a stack
   • Other stack manipulation problems
4. Time and space are both O(n) due to n recursive calls
5. The key insight is that recursion "remembers" the elements we popped
6. This technique can be extended to insert at any position