181. Binary Tree - Preorder Traversal - Non Recursive Approach

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 in an 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, the first traverse the root node then the left node followed by the right node.

Pseudo Code:

1. Create 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 the 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 animated image below and code for more understanding.

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

Related Problems:

- In a Binary Tree, Check if Two nodes has the same parent or are siblings Medium
- Get the Sum of all left leaves in a Binary tree Beginner
- Printing Nodes without Siblings in a Binary Tree Beginner
- Print All Root-to-Leaf Paths in a Binary Tree Medium
- Find the Deepest Node in a Binary Tree Medium