3 Iterative Solutions: Stack And Morris Traversal (Complexity Explained)
1 Stack-based:\nStack-based: \njava\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new Array
### 1 Stack-based:\nStack-based: \n```java\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new ArrayList<>();\n        if (root == null)\n            return res;\n        Stack<TreeNode> s = new Stack<>();\n        s.push(root);\n        while (!s.isEmpty()) {\n            TreeNode cur = s.pop();\n            res.add(cur.val);\n            if (cur.right != null)\n                s.push(cur.right);\n            if (cur.left != null)\n                s.push(cur.left);\n        }\n        return res;\n    }\n}\n```\nPush right before left so that, due to the property of a stack, left is processed before right; This is the logic that echoes most throughout this problem's discussions, and is very easy to understand.\n\n### 2 Stack-based:\nSlight changes. \n```java\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new ArrayList<>();\n        if (root == null)\n            return res;\n        Stack<TreeNode> s = new Stack<>();\n        s.push(root);\n        while (!s.isEmpty()) {\n            TreeNode cur = s.pop();\n            while (cur != null) {\n                res.add(cur.val);\n                s.push(cur.right);\n                cur = cur.left;\n            }\n        }\n        return res;\n    }\n}\n```\nThis algorithm employs a technique I like to call "push horizontal" that is frequently used in the implementation of stack-based InOrder and PostOrder algorithm. Since PreOrder logic is generally easier than the other two, this approach is not as much used as that of solution 1. Note that here we push `cur.right` rather than `cur`. The `null` cases will handle themselves by the inner while loop.\n\n\n### 3 Morris Traversal\n```java\npublic class Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> res = new ArrayList<>();\n        if (root == null)\n            return res;\n        TreeNode cur = root;\n        while (cur != null) {\n            if (cur.left == null) {\n                res.add(cur.val);\n                cur = cur.right;\n            } else {\n                TreeNode prev = cur.left;\n                while (prev.right != null && prev.right != cur)\n                    prev = prev.right;\n                if (prev.right == null) {\n                    res.add(cur.val);\n                    prev.right = cur;\n                    cur = cur.left;\n                } else {\n                    prev.right = null;\n                    cur = cur.right;\n                }\n            }\n        }\n        return res;\n    }\n}\n```\nA [**good explanation**](http://www.geeksforgeeks.org/inorder-tree-traversal-without-recursion-and-without-stack/) here gives implementation of Morris Traversal InOrder algorithm. The PreOrder algorithm can be achieved by tweaking the code very slightly: rather than visit `cur` when we **restore** the tree(which is generally the second time we are at node `cur`), we visit it the first time we encounter it, which is when we have to **modify**. \n\nThe space **complexity** for Morris Traversal is O(1) obviously. The time complexity is actually O(N) which is a little more subtle. The outer while loop is executed O(N) iterations obviously, depending on the position of `root` in the InOrder serialization of the tree. In each such iteration, we have to find the left predecessor for `cur`, which is the costly part. Trivially you would think that gives us `O(NlgN)` per height of the tree. But if you think aggregately, you will see these:\n* For each node, we do `find left predecessor` on it only twice.\n* Throughout these two `find left predecessor` inner while loops, each edge of the tree get traversed at most twice.\n\nYou might have to draw a tree and doodle some trace to convince yourself this. Since a tree has `N-1` edges, with `N` as the number of nodes, we know that the time complexity is O(N).
[]