# Three ways of Iterative Preorder Traversing. Easy Explanation

• Three types of Iterative Preorder Traversals in java.

1. Using 1 Stack. O(n) Time & O(n) Space
• Print and push all `left` nodes into the `stack` till it hits `NULL`.
• Then `Pop` the top element from the stack, and make the `root` point to its `right`.
• Keep iterating till `both` the below conditions are met -
• Stack is empty `and`
• Root is NULL.
``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<Integer>();
if(root==null)
return out;
Stack<TreeNode> s = new Stack();
while(root!=null || !s.empty()){
if(root!=null){
s.push(root);
root = root.left;
}
else{
root = s.pop();
root = root.right;
}
}
return out;
}
``````
1. Using 2 Stacks. O(n) Time & O(n) Space
We use two stacks. Stack `s` is used to find and traverse the child nodes, and `path` stack keeps track of the path from the `root` to the current node. (This is usefull in certain problems like Binary Tree Paths and Path Sum ).
• Initially we push the `root` into `s`.
• Keep iterating with below logic till `s` is `empty`.
• `root` = `s.peek()`
• If the top elements of both the stacks are not the same :
• Print `root` and push it into `path`.
• Push `root`'s children into `s` in reverse order. (Remember it's a stack!)
• When top elements of both stacks are equal. (Which means we hit a deadend, and need to turn back)
• `Pop` from `both` stacks.
``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<Integer>();
if(root == null)
return out;
Stack<TreeNode> s = new Stack(), path = new Stack();
s.push(root);
while(!s.empty()){
root = s.peek();
if(!path.empty() && path.peek()==root){
s.pop();
path.pop();
}
else{
path.push(root);
if(root.right != null)
s.push(root.right);
if(root.left != null)
s.push(root.left);
}
}
return out;
}
``````
1. Using No Stacks (Morris Traversal). O(n) Time & O(1) Space
Instead of using stacks to remember our way back up the tree, we are going to modify the tree to create upwards links. The idea is based on Threaded Binary Tree.
• Iterate till `root` is null.
• If `root` has a left child.
• Find the `inorder predecessor`. (Inorder predecessor of root is the right most child of its left child)
• Make it point to root.
• `root` = `root.left`.
• If its already pointing to root (which means we have traversed it already and are on our way up.)
• Make the `inorder predecessor` point to `null` (Reverting our structural changes)
• `root` = `root.right`.
• If left child is `null`
• `root` = `root.right`. (We are climbing up our link.)
``````public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> out = new ArrayList<Integer>();
if(root == null)
return out;
TreeNode pre = null;
while(root!=null){
if(root.left !=null){
pre = root.left;
while(pre.right!=null && pre.right!=root)
pre=pre.right;
if(pre.right==null){
pre.right=root;
root=root.left;
}
else{
pre.right=null;
root=root.right;
}
}
else{