🔥 [LeetCode The Hard Way]🔥 DFS | Pre Order | Explained Line By Line
\uD83D\uDD34 Check out LeetCode The Hard Way for more solution explanations and tutorials. \n\uD83D\uDFE0 Check out our Discord for live discussion.\n\uD83D\uDF
\uD83D\uDD34 Check out [LeetCode The Hard Way](https://wingkwong.github.io/leetcode-the-hard-way/) for more solution explanations and tutorials. \n\uD83D\uDFE0 Check out our [Discord](https://discord.gg/Nqm4jJcyBf) for live discussion.\n\uD83D\uDFE2 Give a star on [Github Repository](https://github.com/wingkwong/leetcode-the-hard-way) and upvote this post if you like it.\n\uD83D\uDD35 Check out [YouTube Channel](https://www.youtube.com/channel/@leetcodethehardway) if you are interested.\n\n---\n\nYou may also check out my recent DFS solutions on other tree problems.\n\n- [987. Vertical Order Traversal of a Binary Tree](https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/discuss/2527028/leetcode-the-hard-way-easy-dfs-explained-line-by-line)\n- [1448. Count Good Nodes in Binary Tree](https://leetcode.com/problems/count-good-nodes-in-binary-tree/discuss/2511705/leetcode-the-hard-way-dfs-explained-line-by-line)\n- [814. Binary Tree Pruning](https://leetcode.com/problems/binary-tree-pruning/discuss/2537510/leetcode-the-hard-way-easy-dfs-explained-line-by-line)\n- [606. Construct String from Binary Tree](https://leetcode.com/problems/construct-string-from-binary-tree/discuss/2542523/leetcode-the-hard-way-dfs-5-cases-explained-line-by-line)\n\nThe steps for pre-order is \n- do something with root value\n- traverse left subtree \n-  traverse right sub tree. \n\nFor example 1, starting the root node 1.\n\n - At node 1 now, add root value which is 1. answer = [1]\n- At node 1 now, traverse left node, however, there is no left node, hence return.\n- At node 1 now, traverse right node.\n- At node 2 now, add root value which is 2. answer = [1, 2]\n- At node 2 now, traverse left node.\n- At node 3 now, add root value which is 3. answer = [1, 2, 3]\n- At node 3 now, traverse left node, however, there is no left node, hence return.\n- At node 3 now, traverse right node, however, there is no right node, hence return.\n- At node 2 now, traverse right node, however, there is no right node, hence return.\n\n**C++**\n\n```cpp\n// Time Complexity: O(N)\n// Space Complexity: O(N)\n\n// This is a standard pre-order traversal problem, I\'d suggest to learn in-order and post-order as well.\n// Here\'s a short tutorial if you\'re interested.\n// https://wingkwong.github.io/leetcode-the-hard-way/tutorials/graph-theory/binary-tree\n// then you may try the following problems \n// 94. Binary Tree Inorder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/\n// 145. Binary Tree Postorder Traversal: https://leetcode.com/problems/binary-tree-postorder-traversal/\n\nclass Solution {\npublic:\n    vector<int> ans;\n    void preorder(TreeNode* node) {\n        if (node == NULL) return;\n        // do something with node value here\n        ans.push_back(node->val);\n        // traverse the left node\n        preorder(node->left);\n        // traverse the right node\n        preorder(node->right);\n    }\n    \n    vector<int> preorderTraversal(TreeNode* root) {\n        preorder(root);\n        return ans;\n    }\n};\n```\n\n**Python**\n\n```py\n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\n\n# This is a standard pre-order traversal problem, I\'d suggest to learn in-order and post-order as well.\n# Here\'s a short tutorial if you\'re interested.\n# https://wingkwong.github.io/leetcode-the-hard-way/tutorials/graph-theory/binary-tree\n# then you may try the following problems \n# 94. Binary Tree Inorder Traversal: https://leetcode.com/problems/binary-tree-inorder-traversal/\n# 145. Binary Tree Postorder Traversal: https://leetcode.com/problems/binary-tree-postorder-traversal/\n\nclass Solution:\n    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n\t\t# root -> left  -> right\n        return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []\n```
['Recursion', 'C', 'Python', 'C++', 'Python3']