Inorder Traversal Without Using Recursion
By admin on May 09, 2016
Category:
Problem:
Inorder Traversal Without Using Recursion
Approach:
We can use a stack data structure to do this:
- Initialize current node as root
- Create a stack.
-
Do following until current is NULL and stack is empty:
- Push the current node to stack and set current = current.left until current is NULL
-
If current is NULL and stack is not empty then
- Pop the top item from stack into current.
- Print current,
- Set current = current.right
Solution:
void inorder(TreeNode n)
{
TreeNode current = n;
Stack s = new Stack();
while((current ! = null) || !s.isEmpty())
{
if(current!=null)
{
s.push(current);
current = current.left;
}
else{
current = s.pop();
print(current);
current = current.right;
}
}
}
Complexity
Time complexity is O(n)
Extra space for stack also will be taken.