Three ways of Iterative Preorder Traversing. Easy Explanation
Three types of Iterative Preorder Traversals in java. \n\n1) Using 1 Stack. O(n) Time & O(n) Space\n\t Print and push all left nodes into the stack till it hits
Three types of Iterative Preorder Traversals in java. \n\n1) **Using 1 Stack.** O(n) Time & O(n) Space\n\t* Print and push all `left` nodes into the `stack` till it hits `NULL`.\n\t* Then `Pop` the top element from the stack, and make the `root` point to its `right`.\n\t* Keep iterating till `both` the below conditions are met -\n\t\t* Stack is empty `and`\n        * Root is NULL.\n\t\n\n```\n\npublic List<Integer> preorderTraversal(TreeNode root) {\n\t\tList<Integer> out = new ArrayList<Integer>();\n\t\tif(root==null)\n\t\t\treturn out;\n\t\tStack<TreeNode> s = new Stack();      \n\t\twhile(root!=null || !s.empty()){\n\t\t\tif(root!=null){\n\t\t\t\tout.add(root.val);\n\t\t\t\ts.push(root);\n\t\t\t\troot = root.left;\n\t\t\t}\n\t\t\telse{\n\t\t\t\troot = s.pop();\t\t\t\t\n\t\t\t\troot = root.right;\n\t\t\t}\n\t\t}\n\t\treturn out;\n\t}\n\t\n```\n\n2) **Using 2 Stacks.** O(n) Time & O(n) Space\nWe 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](https://leetcode.com/problems/binary-tree-paths/) and [Path Sum](https://leetcode.com/problems/path-sum/) ). \n    * Initially we push the `root` into `s`.\n\t* Keep iterating with below logic till `s` is `empty`.\n\t\t* `root` = `s.peek()`\n\t\t* If the top elements of both the stacks are not the same :\t\t\n\t\t\t* Print `root` and push it into `path`.\n\t\t\t* Push `root`\'s children into `s` in reverse order. (Remember it\'s a stack!)\n\t\t* When top elements of both stacks are equal. (Which means we hit a deadend, and need to turn back)\n\t\t\t* `Pop` from `both` stacks.\n\t\n\t\n```\n\npublic List<Integer> preorderTraversal(TreeNode root) {\n\t\tList<Integer> out = new ArrayList<Integer>();\n        if(root == null)\n            return out; \n        Stack<TreeNode> s = new Stack(), path = new Stack();\n        s.push(root);\n        while(!s.empty()){\n            root = s.peek();\n            if(!path.empty() && path.peek()==root){\n                s.pop();\n                path.pop();\n            }\n            else{\n                out.add(root.val);\n                path.push(root);\n                if(root.right != null)\n                    s.push(root.right);\n                if(root.left != null)\n                    s.push(root.left);\n            }\n        }\n\t    return out;\n    }\n\t\n```\n\n3) **Using No Stacks (Morris Traversal).** O(n) Time & O(1) Space\nInstead 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](https://en.wikipedia.org/wiki/Threaded_binary_tree). \n\t* Iterate till `root` is null.\n\t\t* If `root` has a left child.\n\t\t\t* Find the `inorder predecessor`. (Inorder predecessor of root is the right most child of its left child)\n\t\t\t\t* Make it point to root.\n\t\t\t\t* `root` = `root.left`.\n\t\t\t* If its already pointing to root (which means we have traversed it already and are on our way up.)\n\t\t\t\t* Make the `inorder predecessor` point to `null` (Reverting our structural changes)\n\t\t\t\t* `root` = `root.right`.\n\t\t* If left child is `null`\n\t\t\t* `root` = `root.right`. (We are climbing up our link.)\n\n\t\t\t\n```\n\npublic List<Integer> preorderTraversal(TreeNode root) {\n\t\tList<Integer> out = new ArrayList<Integer>();\n\t\tif(root == null)\n\t\t\treturn out;\n\t\tTreeNode pre = null;\n\t\twhile(root!=null){\n\t\t\tif(root.left !=null){\n\t\t\t\tpre = root.left;\n\t\t\t\t\twhile(pre.right!=null && pre.right!=root)\n\t\t\t\t\tpre=pre.right;\n\t\t\t\tif(pre.right==null){\n\t\t\t\t\tout.add(root.val);\n\t\t\t\t\tpre.right=root;\n\t\t\t\t\troot=root.left;\n\t\t\t\t}\n\t\t\t\telse{\n\t\t\t\t\tpre.right=null;\n\t\t\t\t\troot=root.right;\n\t\t\t\t}                   \n\t\t\t}\n\t\t\telse{\n\t\t\t\tout.add(root.val);\n\t\t\t\troot=root.right;\n\t\t\t}\n\t\t}\n\t\treturn out;\n\t}\n\t\n```\n\nAlso checkout [Inorder](https://discuss.leetcode.com/topic/64682/three-ways-of-iterative-inorder-traversing-easy-explanation)  & [PostOrder](https://discuss.leetcode.com/topic/64689/three-ways-of-iterative-postorder-traversing-easy-explanation)  :))
[]