• Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.

### Preorder Traversal:

This is simple. In Preorder Traversal we first visit the current node, then the entire left subtree before visiting right child. Since this is iterative implementation, we would definitely need a stack. So let's see step by step how to build the iterative preorder algorithm implementation:

Step#0. Initialization: Initialize the stack by pushing root node in it. That way root now is in line to be processed.
Step#1. Visit the current node. The current node will be at the top of the stack. So just pop the stack.
Step#2. We need to process the entire left subtree next, before processing right child node (and right sub tree). This means, push left child of the current node in the stack.
Step#3. Now push right child of the current node in the stack so that this node is in the stack and will be visited once the left subtree of the current node is done processing.

Let's look at the code now:

Java code:

``````
public List<Integer> preorder(Node root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<Node> stack = new ArrayDeque<>();
while (!stack.isEmpty()) {
// visit
Node currNode = stack.removeLast();
// process

if (currNode.right != null) {
}
if (currNode.left != null) {
}
}
return res;
}
``````

Python Code:

#### The above content is written by: 