Objective: Given a binary tree, write a non recursive or iterative algorithm for preorder traversal.
Example:
Earlier we have seen “What is preorder 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 preorder traversal is, first traverse the root node then left node followed by the right node.
Pseudo Code:
- Create a Stack.
- Print the root and push it to Stack and go left i.e root=root.left and 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.
- 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 PreOrderTree { | |
| public void preOrderRecursive(Node root) { | |
| if (root != null) { | |
| System.out.print(root.data + " "); | |
| preOrderRecursive(root.left); | |
| preOrderRecursive(root.right); | |
| } | |
| } | |
| public void preorderIteration(Node root) { | |
| Stack<Node> s = new Stack<Node>(); | |
| while (true) { | |
| // First print the root node and then add left node | |
| while (root != null) { | |
| System.out.print(root.data + " "); | |
| s.push(root); | |
| root = root.left; | |
| } | |
| // check if Stack is emtpy, if yes, exit from everywhere | |
| if (s.isEmpty()) { | |
| return; | |
| } | |
| // pop the element from the stack and go right to the tree | |
| root = s.pop(); | |
| 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); | |
| root.right.left = new Node(6); | |
| root.right.right = new Node(7); | |
| PreOrderTree i = new PreOrderTree(); | |
| i.preOrderRecursive(root); | |
| System.out.println(); | |
| i.preorderIteration(root); | |
| } | |
| } | |
| class Node { | |
| int data; | |
| Node left; | |
| Node right; | |
| public Node(int data) { | |
| this.data = data; | |
| } | |
| } |
Output:
1 2 4 5 3 6 7 1 2 4 5 3 6 7
if (root == null) {
root = stack.pop();
root = root.right;
}
we need to pop from stack when root is null in iterative traversal. Please correct that.
Another solution same as Non Recursive Post Order Traversal
//Non-recursive pre order traversal
private void nonRecursivePreOrderTraversal(Node root) {
if (root != null) {
System.out.println(“Non Recursive Pre Order Traversal:”);
Stack stack1 = new Stack();
//Push root node
stack1.push(root);
while(!stack1.isEmpty()) {
//Pop from stack1
NodepoppedNode = stack1.pop();
System.out.print(poppedNode.data + “->”);
//Push right
if (poppedNode.right != null) {
stack1.push(poppedNode.right);
}
//Push left
if (poppedNode.left != null) {
stack1.push(poppedNode.left);
}
}
}
}