Objective: Given a binary tree, write a non recursive or iterative algorithm for Inorder traversal.
Example:
Earlier we have seen “What is Inorder traversal and recursive algorithm for it“, In this article we will solve it with iterative/Non Recursive manner.
Since we are not using recursion, we will use the Stack to store the traversal, we need to remember that inorder traversal is, first traverse the left node then root followed by the right node.
Pseudo Code:
- Create a Stack.
- Push the root into the stack and set the root = root.left continue till it hits the NULL.
- If root is null and Stack is empty Then
- return, we are done.
- Else
- Pop the top Node from the Stack and set it as, root = popped_Node.
- print the root and go right, root = root.right.
- Go to step 2.
- End If
See the animated image below and code for more understanding.
Complete Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Stack; | |
public class InorderIretation { | |
public void inorderRecursive(Node root) { | |
if (root != null) { | |
inorderRecursive(root.left); | |
System.out.print(root.data + " "); | |
inorderRecursive(root.right); | |
} | |
} | |
public void inorderIteration(Node root) { | |
Stack<Node> s = new Stack<Node>(); | |
while (true) { | |
// Go to the left extreme insert all the elements to stack | |
while (root != null) { | |
s.push(root); | |
root = root.left; | |
} | |
// check if Stack is empty, if yes, exit from everywhere | |
if (s.isEmpty()) { | |
return; | |
} | |
// pop the element from the stack , print it and add the nodes at | |
// the right to the Stack | |
root =s.pop(); | |
System.out.print(root.data + " "); | |
root = root.right; | |
} | |
} | |
public static void main(String[] args) { | |
Node root = new Node(1); | |
root.left = new Node(2); | |
root.right = new Node(3); | |
root.left.left = new Node(4); | |
root.left.right = new Node(5); | |
InorderIretation i = new InorderIretation(); | |
i.inorderRecursive(root); | |
System.out.println(); | |
i.inorderIteration(root); | |
} | |
} | |
class Node { | |
int data; | |
Node left; | |
Node right; | |
public Node(int data) { | |
this.data = data; | |
} | |
} |
Output:
4 2 5 1 3 4 2 5 1 3