Java || 👍Explained in Detail👍|| Simple & Fast Solution✅|| Recursive & Iterative
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this helpful, please \uD83D\uDC4D upvote this post a
I do my best everyday to give a clear explanation, so to help everyone improve their skills.\n\nIf you find this **helpful**, please \uD83D\uDC4D **upvote** this post and watch my [Github Repository](https://github.com/cheehwatang/leetcode-java).\n\nThank you for reading! \uD83D\uDE04 Comment if you have any questions or feedback.\n\n---\n\n# Approach\n\nAlgorithm for Preorder(tree)\n   1. Visit the root.\n   2. Traverse the left subtree\n   3. Traverse the right subtree\n\nExample:\n![image](https://assets.leetcode.com/users/images/3d49dfe8-0dd8-4537-8636-0a6f1a035377_1663136628.9607692.png)\nSteps:\n1. At node 1 now, add root value 1 => Integers[1]\n2. At node 1 now, traverse the left node.\n3. At node 2 now, add root value 2 => Integers[1, 2]\n4. At node 2 now, traverse the left node.\n5. At node 4 now, add root value 4 => Integers[1, 2, 4]\n6. At node 4 now, traverse the left node. Since no left node (null), return to node 4.\n7. At node 4 now, traverse the right node. Since no right node (null), return to node 4, then node 2.\n8. At node 2 now, traverse the right node.\n9. At node 5 now, add root value 5 => Integers[1, 2, 4, 5]\n10. At node 5 now, traverse the left node. Since no left node (null), return to node 5.\n11. At node 5 now, traverse the right node. Since no right node (null), return to node 5, then node 2, then node 1.\n12. At node 1 now, traverse the riht node.\n13. At node 3 now, add root value 3 => Integers[1, 2, 4, 5, 3]\n14. At node 3 now, traverse the left node. Since no left node (null), return to node 3.\n15. At node 3 now, traverse the right node. Since no right node (null), end traversal.\n\nAs shown, each node here has the traversal sequence of root -> left -> right.\n\n---\n\n# Recursive Implementation:\n\n## Complexity\n- Time Complexity  : O(n), \nwhere \'n\' is the number of nodes in the tree, as we are traversing every single node.\nHowever, this does not take into account the resizing of the array backing the LinkedList, depending on the size of nodes in the tree.\n\n- Space Complexity : O(n), \nwhere \'n\' is the number of nodes in the tree, as we are recording the value of every node into the List.\nThe recursive call stack only takes up the maximum space of tree height, which is smaller than \'n\'.\n\n## Java - With Explanation (Recursive)\n\n```\nclass Solution {\n\n    // Wrapper method to set up and initialize the recursive function.\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> integerList = new LinkedList<>();\n        integerList = preorderTraversal(root, integerList);\n        return integerList;\n    }\n\n    // Recursive method.\n    private List<Integer> preorderTraversal(TreeNode root, List<Integer> integerList) {\n        // The base case, for when the root is null.\n        if (root == null) return integerList;\n\n        // For preorder traversal, we first visit the root and add the value of the root to the list.\n        integerList.add(root.val);\n        // Then, we visit the left node.\n        preorderTraversal(root.left, integerList);\n        // Lastly, we visit the right node.\n        preorderTraversal(root.right, integerList);\n\n        // Once done, we return the list.\n        return integerList;\n    }\n}\n```\n\n## Java - Clean Code (Recursive)\n\n```\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> integerList = new LinkedList<>();\n        integerList = preorderTraversal(root, integerList);\n        return integerList;\n    }\n\n    private List<Integer> preorderTraversal(TreeNode root, List<Integer> integerList) {\n        if (root == null) return integerList;\n\n        integerList.add(root.val);\n        preorderTraversal(root.left, integerList);\n        preorderTraversal(root.right, integerList);\n\n        return integerList;\n    }\n}\n```\n\n---\n\n# Iterative Implementation:\n\n## Complexity\n- Time Complexity  : O(n), \nwhere \'n\' is the number of nodes in the tree, as we are traversing every single node.\nHowever, this does not take into account the resizing of the array backing the LinkedList, depending on the size of nodes in the tree.\n\n- Space Complexity : O(n), \nwhere \'n\' is the number of nodes in the tree, as we are recording the data of every node into the List.\nThe stack only takes up the maximum space of tree height, which is smaller than \'n\'.\n\n## Java - With Explanation (Iterative)\n\n```\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> integerList = new LinkedList<>();\n        Stack<TreeNode> rightNodes = new Stack<>();\n\n        while (root != null) {\n            // First, we record the root.\n            integerList.add(root.val);\n\n            // If right node is available, push the right node into the Stack first.\n            // We will pop it later we are done with the left nodes.\n            if (root.right != null) {\n                rightNodes.push(root.right);\n            }\n\n            // Continue to traverse to the left, while recording each subtree root nodes,\n            // and pushing the subtree right nodes into the stack.\n            // Once reaches a leaf node, pop the right nodes and continue.\n            root = root.left;\n            if (root == null && !rightNodes.isEmpty()) {\n                root = rightNodes.pop();\n            }\n        }\n        // Fully traversed the tree.\n        return integerList;\n    }\n}\n```\n\n## Java - Clean Code (Iterative)\n\n```\nclass Solution {\n    public List<Integer> preorderTraversal(TreeNode root) {\n        List<Integer> integerList = new LinkedList<>();\n        Stack<TreeNode> rightNodes = new Stack<>();\n\n        while (root != null) {\n            integerList.add(root.val);\n\n            if (root.right != null) {\n                rightNodes.push(root.right);\n            }\n\n            root = root.left;\n            if (root == null && !rightNodes.isEmpty()) {\n                root = rightNodes.pop();\n            }\n        }\n        return integerList;\n    }\n}\n```
['Binary Search', 'Stack', 'Depth-First Search', 'Binary Tree', 'Java']