## Iterative preorder traversal

In last post Iterative inorder traversal , we learned how to do inorder traversal of binary tree without recursion or in iterative way. Today we will learn how to do iterative preorder traversal of binary tree. In preorder traversal, root node is processed before left and right subtrees. For example, preorder traversal of below tree would be [10,5,1,6,14,12,15], We already know how to implement preorder traversal in recursive way, let’s understand how to implement it in non-recursive way.

## Thought process for preorder traversal

If we look at recursive implementation, preorder traversal is: process the root, left subtree, and then right subtree.

Once the left subtree is processed, control goes to the first node in the right subtree. To emulate this behavior in a non-recursive way, it is best to use a stack. What and when push and pop will happen on the stack?
Start with pushing the root node to stack. Traversal continues till there is at least one node onto the stack.

Pop the root node from stack,process it and push it’s right and left child on to stack. Why right child before left child? Because we want to process left subtree before right subtree. As at every node, we push it’s children onto stack, entire left subtree of node will be processed before right child is popped from the stack. Algorithm is very simple and is as follows.

2. While there stack is not empty
1. Pop from stack `current ` = s.pop() and process the node.
2. Push `current.right` onto to stack.
3. Push `current.left` onto to stack.

Let’s take and example and see how it works. Given below tree, do preorder traversal on it without recursion. Let’s start from root node(10) and push it onto stack. current = node(10). Here loop starts, which checks if there is node onto stack. If yes, it pops that out. s.pop will return node(10), we will print it and push it’s right and left child onto stack. Preorder traversal till now : . Since stack is not empty, pop from it.current= node(5). Print it and push it’s right and left child i.e node(6) and node(1) on stack. Again, stack is not empty, pop from stack. current  = node(1). Print node. There is no right and left child for this node, so we will not push anything on the stack. Stack is not empty yet, pop again. current= node(6). Print node. Similar to node(1), it also does not have right or left subtree, so nothing gets pushed onto stack. However, stack is not empty yet. Pop. Current = node(14). Print node, and as there are left and right children, push them onto the stack as a right child before left child. Stack is not empty, so pop from stack, current = node(12). Print it, as there are no children of node(12), push nothing to stack. Pop again from the stack as it not empty. current = node(15). Print it. No children, so no need to push anything. At this point, the stack becomes empty and we have traversed all node of the tree also.

### Implementation

``` public void preorder(TreeNode root){
Stack<TreeNode> stack = new Stack<>();

if(root == null) return ;

TreeNode currentNode = null;
stack.push(root);

while(!stack.isEmpty()){
/* Step 5 : Pop the node */
currentNode = stack.pop();

/* Step 2 : Print the node */
System.out.println(currentNode.getValue());

/* Step 3: Push right child first */
if(currentNode.getRight() != null){
stack.push(currentNode.getRight());
}
/* Step 4: Push left child */
if(currentNode.getLeft() != null){
stack.push(currentNode.getLeft());
}
}
}
```

The complexity of iterative implementation of preorder traversal of a binary tree is O(n) as we will be visiting each node at least once. Also, there is added space complexity of stack which is O(n).

Please share if there is something wrong or missing. If you are willing to contribute and share your knowledge with thousands of learners across the world, please reach out to us at [email protected]