Insert an Element at the Bottom of a Stack : Want to master stacks? This beginner-friendly tutorial walks you through how to insert an element at the bottom of a stack using recursion — without any extra data structures!
You’ll learn:
✅ What the problem means
✅ How recursion helps you simulate going deep into the stack
✅ Step-by-step explanation with dry run
✅ Full working code in C++ and Python
✅ Practice exercises to test your understanding
Perfect for beginners preparing for coding interviews or learning recursion concepts with stacks. Start building your foundation in data structures now!
Problem Statement Insert an Element at the Bottom of a Stack:
“Given a stack and an element, insert that element at the bottom of the stack.”
Example:
Input: Stack =5 4 3 2 1, Element to Insert =10
Output: Stack =10 5 4 3 2 1
Concepts You’ll Learn:
- Stack basics
- Recursion
- How function calls can act like a temporary stack
Approach for :
Step-by-step solution for Insert an Element at the Bottom of a Stack:
- If the stack is empty, push the given element. ✅
- Otherwise:
- Pop the top element temporarily.
- Recur to insert the element at the bottom.
- Push the popped elements back after inserting. 🔄
This way, you dig down to the bottom using recursion, then insert, and rebuild the stack on your way back up.
C++ Code for Insert an Element at the Bottom of a Stack
#include <iostream>
#include <stack>
using namespace std;
// Function to insert element at the bottom of a stack
void insertAtBottom(stack<int>& st, int element) {
// Base case: stack is empty
if (st.empty()) {
st.push(element);
return;
}
// Step 1: Pop top element
int top = st.top();
st.pop();
// Step 2: Recursive call
insertAtBottom(st, element);
// Step 3: Push top back after inserting
st.push(top);
}
int main() {
stack<int> st;
// Push some elements
st.push(1);
st.push(2);
st.push(3);
st.push(4);
st.push(5);
int newElement = 10;
insertAtBottom(st, newElement);
// Display stack
cout << "Stack after inserting at bottom:\n";
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
return 0;
}
Python Code for Insert an Element at the Bottom of a Stack
def insert_at_bottom(stack, element):
# Base case: if stack is empty, insert element
if not stack:
stack.append(element)
return
# Step 1: Remove top
top = stack.pop()
# Step 2: Recursive call
insert_at_bottom(stack, element)
# Step 3: Put back the top
stack.append(top)
# Test
stack = [1, 2, 3, 4, 5]
element = 10
insert_at_bottom(stack, element)
print("Stack after inserting at bottom:")
print(stack[::-1]) # Print from top to bottom
Dry Run Example (Simple):
Let’s dry run the C++/Python code for inserting an element at the bottom of a stack, step by step.
Input:
Initial Stack (top -> bottom): [5, 4, 3, 2, 1]
Element to insert at bottom: 10
Function Call:
insertAtBottom(st, 10);
Dry Run – Step by Step (Recursion Unwinding)
Stack Before:
[top] → 5 → 4 → 3 → 2 → 1 → [bottom]
Step 1:
st.top() is 5
Pop 5 → Recur on smaller stack
Call: insertAtBottom([4, 3, 2, 1], 10)
Step 2:
Pop 4 → Recur again
Call: insertAtBottom([3, 2, 1], 10)
Step 3:
Pop 3 → Recur again
Call: insertAtBottom([2, 1], 10)
Step 4:
Pop 2 → Recur again
Call: insertAtBottom([1], 10)
Step 5:
Pop 1 → Recur again
Call: insertAtBottom([], 10)
Step 6 (Base Case):
Stack is empty
→ Push 10
✅ Stack: [10]
Backtracking Begins (Pushing elements back):
Now we return from previous function calls one-by-one:
Return to Step 5:
Push 1 → Stack: [1, 10]
Return to Step 4:
Push 2 → Stack: [2, 1, 10]
Return to Step 3:
Push 3 → Stack: [3, 2, 1, 10]
Return to Step 2:
Push 4 → Stack: [4, 3, 2, 1, 10]
Return to Step 1:
Push 5 → Stack: [5, 4, 3, 2, 1, 10]
Final Stack (Top to Bottom):
[top] → 5 → 4 → 3 → 2 → 1 → 10 → [bottom]
🎉 Success! We inserted 10 at the bottom of the stack without using extra space
Why Use Recursion?
Stacks follow Last-In-First-Out (LIFO) — meaning you can only directly access or modify the top of the stack. There’s no built-in way to reach the bottom element directly.
But recursion gives us a trick:
- It lets us temporarily pop all elements one by one.
- Then, after reaching the empty stack (i.e., bottom), we insert the new element.
- Finally, recursion rebuilds the original stack by pushing the saved elements back.
So, recursion simulates going deep into the stack, allowing us to insert at the bottom without breaking the stack’s rules!
Practice Exercises (to solidify your learning):
🔁 1. Reverse a stack using the insert_at_bottom() method.
💡 Tip: Use recursion to pop all elements, then reinsert using your insert-at-bottom function.
🔁 2. Insert an element at the bottom without using recursion, by using:
- A second temporary stack, or
- A queue (FIFO nature)
🔁 3. Implement stack reversal using both iterative and recursive approaches.
🔁 4. Write a function to find the size of a stack recursively.
🔁 5. Use insert_at_bottom() to sort a stack recursively in increasing order.
Leave a Reply