Binary Tree — Preorder Traversal — Non Recursive Approach

Objec­tive: Given a binary tree, write a non recur­sive or iter­a­tive algo­rithm for pre­order tra­ver­sal.

Tree Tra­ver­sals — Preorder

Exam­ple:

Ear­lier we have seen “What is pre­order tra­ver­sal and recur­sive algo­rithm for it”, In this arti­cle we will solve it with iterative/Non Recur­sive manner.

Since we are not using recur­sion, we will use the Stack to store the tra­ver­sal, we need to remem­ber that pre­order tra­ver­sal is, first tra­verse the root node then left node fol­lowed by the right node.

Pseudo Code:

1. Cre­ate a Stack.
2. Print the root and push it to Stack and go left i.e root=root.left and till it hits the NULL.
3. If root is null and Stack is empty Then
1. return, we are done.
4. Else
1. Pop the top Node from the Stack and set it as, root = popped_Node.
2. Go right, root = root.right.
3. Go to step 2.
5. End If

See the ani­mated image below and code for more understanding.

Pre­order traversal

Com­plete Code:

Out­put:

```1 2 4 5 3 6 7
1 2 4 5 3 6 7
```

You may also like...

• Bandla palli Bhukailas Reddy

if (root == null) {
root = stack.pop();
root = root.right;
}

we need to pop from stack when root is null in iter­a­tive tra­ver­sal. Please cor­rect that.

• lipsa patel

Another solu­tion same as Non Recur­sive Post Order Traversal

//Non-recursive pre order tra­ver­sal
pri­vate void nonRecursivePreOrderTraversal(Node root) {
if (root != null) {

System.out.println(“Non Recur­sive Pre Order Tra­ver­sal:”);
Stack stack1 = new Stack();

//Push root node
stack1.push(root);

while(!stack1.isEmpty()) {
//Pop from stack1
Node­poppedNode = 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);
}
}
}
}