In this tutorial, I am going to discuss binary tree inorder traversal without recursion.
Given a binary tree, write a code to print the Inorder traversal of a binary tree node values.
What is Binary Tree Inorder Traversal?
Traversing a tree means visiting each node of the tree exactly once. In inorder traversal, we visit the tree in following order.
i) Visit all the nodes of the left subtree.
ii) Visit root node.
iii) Visit all the nodes of the right subtree.
Get minimum element from stack in O(1).
In this problem, we have to design a stack that supports push, pop, top, and retrieving the minimum element in constant time (O(1)).
push(x) — Push element x onto stack.
pop() — Removes the element on top of the stack.
top() — Get the top element.
getMin() — Retrieve the minimum element in the stack.
For example: Suppose, If we push the following elements in a stack.
9 ==> Top
1
2
3
Then if we call getMin() method, It should return 1 in O(1) (constant time).
How to implement a queue using two stacks. In this tutorial, I am going to discuss how to implement a first in first out (FIFO) queue using only two stacks.
In this problem, we are going to implement following methods of QueueUsingStack class:
void push(int x) – Insert an element x.
int pop() – Removes the element (In FIFO order).
int peek() – Returns the element which is present at the front of the queue.
boolean empty() – Returns true if no element is present else false.
For example –
|
1 2 3 4 5 6 |
QueueUsingStack qu = new QueueUsingStack(); qu.push(5); // Element in queue is : [5] qu.push(4); // elements are : [5, 4] qu.peek(); // return 5 qu.pop(); // return 5, queue is [4] qu.empty(); // return false |