JAVAJEE.COM
Engineering Full Stack Apps with Java and JavaScript
Inorder Traversal Without Using Recursion
Normal Login
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.
- heartin's blog
- Log in or register to post comments