Easy , Beginner friendly & Dry run ||Pre Order Traversal || Time O(n) & Space O(n) || Gits✅✅😎😎
Guys if the solution and explanation is helpful the upvote me.\u2764\uFE0F\u2764\uFE0F\n\n\n\n# Approach \uD83D\uDC48\n\n- In the question given, the root of a 
# Guys if the solution and explanation is helpful the upvote me.\u2764\uFE0F\u2764\uFE0F\n\n![Screenshot 2024-02-05 114830.png](https://assets.leetcode.com/users/images/265d4aa0-efe4-458b-90b9-71a57153caac_1707117581.8208427.png)\n\n# Approach \uD83D\uDC48\n\n- In the question given, the root of a binary tree is provided, and the goal is to return a list of the nodes\' values in pre-order traversal. We will use recursion to solve this problem.\n\n- To accomplish a pre-order traversal, we need to understand its process, which involves recursively going through all nodes of the tree by first visiting the root node, then the left subtree, and finally the right subtree.\n\n# What is Pre-Order traversal - \uD83D\uDC48\n\n- In preorder traversal, first, root node is visited, then left sub-tree and after that right sub-tree is visited. The process of preorder traversal can be represented as -\n        `root \u2192 left \u2192 right`  \n\n- Root node is always traversed first in preorder traversal, while it is the last item of postorder traversal. Preorder traversal is used to get the prefix expression of a tree.\n\n# How does Pre-Order Traversal of Binary Tree Work? \uD83D\uDC48\n\nConsider the following tree:\n\n![Screenshot 2024-02-04 213305.png](https://assets.leetcode.com/users/images/1d6e8cdb-ba98-48a9-9bc2-6d33bd8bb2e3_1707116164.4112926.png)\n\n**Step 1:** \n- At first the root will be visited, i.e. node 1.\n\n![image.png](https://assets.leetcode.com/users/images/73abdb99-f8e4-406b-a200-aefd15df01b3_1707116196.6528141.png)\n\n**Step 2:** \n- After this, traverse in the left subtree. Now the root of the left subtree is visited i.e., node 2 is visited.\n\n![image.png](https://assets.leetcode.com/users/images/a2df869b-56ae-4fb7-ab63-82b62907b3ef_1707116258.9549341.png)\n\n**Step 3:** \n- Again the left subtree of node 2 is traversed and the root of that subtree i.e., node 4 is visited.\n\n![image.png](https://assets.leetcode.com/users/images/bf5589b6-19b3-4347-8a13-13b9fb02960a_1707116319.836879.png)\n\n**Step 4:** \n- There is no subtree of 4 and the left subtree of node 2 is visited. So now the right subtree of node 2 will be traversed and the root of that subtree i.e., node 5 will be visited.\n\n![image.png](https://assets.leetcode.com/users/images/bcf64bb1-2264-4b4d-b2f9-938e6dcd5d90_1707116380.6992848.png)\n\n**Step 5:** \n- The left subtree of node 1 is visited. So now the right subtree of node 1 will be traversed and the root node i.e., node 3 is visited.\n\n![image.png](https://assets.leetcode.com/users/images/b5590dbc-fcc7-4d7b-a497-f47d41de3237_1707116416.5990686.png)\n\n**Step 6:**\n- Node 3 has no left subtree. So the right subtree will be traversed and the root of the subtree i.e., node 6 will be visited. After that there is no node that is not yet traversed. So the traversal ends.\n\n![image.png](https://assets.leetcode.com/users/images/24cc2ca4-a89d-4ee4-96ce-37d37a22aeb7_1707116456.0454617.png)\n\nSo the order of traversal of nodes is 1 -> 2 -> 4 -> 5 -> 3 -> 6.\n\n# Code Explanation: \uD83D\uDC48\n\n**The helper Method:** \n- This method is designed to perform the recursive pre-order traversal. It accepts a TreeNode (representing the current node being visited) and an ArrayList<Integer> (to collect the values of the nodes in pre-order).\n \n- The method works as follows:\n\n    - **Base Case:** If the current node (root) is null, it returns immediately, as there is nothing to process. This condition is crucial for ending the recursion, especially when dealing with leaf nodes\' children, which are null.\n\n    - **Process the Current Node:** If the current node is not null, its value is added to the ans list. This step corresponds to the "Root" part of the pre-order traversal.\n\n    - **Recursive Calls:** The method then makes recursive calls first to the left child (helper(root.left, ans)) and then to the right child (helper(root.right, ans)). These calls ensure that all nodes in the left subtree are visited before moving to the right subtree, adhering to the pre-order traversal order.\n\n**The preorderTraversal Method:** \n- This is the public method that initiates the traversal. It does the following:\n\n    - **Initialize the ArrayList:** An ArrayList<Integer> named ans is created to store the values of the nodes visited during the traversal.\n\n    - **Check for Empty Tree:** If the input root is null, indicating an empty tree, the method returns the empty ans list immediately.\n\n    - **Start Recursive Traversal:** If the tree is not empty, it calls the helper method with the root of the tree and the ans list. After this method call completes, ans will contain the values of all the nodes in pre-order.\n\n    - **Return the List:** Finally, the method returns the ans list, which now holds the result of the pre-order traversal.\n\n# Complexity \uD83D\uDC48\nTime complexity: O(n)\n\nSpace complexity: O(log n) to O(n)\n\n# Code \uD83D\uDC48\n```C++ []\n/**\n * Definition for a binary tree node.\n * struct TreeNode {\n *     int val;\n *     TreeNode *left;\n *     TreeNode *right;\n *     TreeNode() : val(0), left(nullptr), right(nullptr) {}\n *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}\n *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}\n * };\n */\nclass Solution {\npublic:\n    void helper(TreeNode* root ,vector<int>& arr){\n        if(root == NULL)return ;\n        arr.push_back(root->val);\n        helper(root->left , arr);\n        helper(root->right , arr);\n    }\n    vector<int> preorderTraversal(TreeNode* root) {\n        vector<int>arr;\n        if(root == NULL)return arr;\n        helper(root , arr);\n        return arr;\n    }\n};\n```\n```Java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public void helper(TreeNode root , ArrayList<Integer> ans){\n        if(root == null)return;\n        ans.add(root.val);\n        helper(root.left , ans);\n        helper(root.right , ans);\n    }\n    public List<Integer> preorderTraversal(TreeNode root) {\n        ArrayList<Integer> ans = new ArrayList<>();\n        if(root == null)return ans;\n        helper(root , ans);\n        return ans;\n    }\n}\n```\n```javascript []\n/**\n * Definition for a binary tree node.\n * function TreeNode(val, left, right) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.left = (left===undefined ? null : left)\n *     this.right = (right===undefined ? null : right)\n * }\n */\n/**\n * @param {TreeNode} root\n * @return {number[]}\n */\nfunction helper(root, ans) {\n    if (root === null) return;\n    ans.push(root.val); \n    helper(root.left, ans);     \n    helper(root.right, ans); \n}\nvar preorderTraversal = function(root) {\n    const ans = []\n    if(root === null)return ans\n    helper(root , ans)\n    return ans\n};\n```\n```C# []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     public int val;\n *     public TreeNode left;\n *     public TreeNode right;\n *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\npublic class Solution {\n    public void helper(TreeNode root , IList<int> ans){\n        if(root == null)return;\n        ans.Add(root.val);\n        helper(root.left , ans);\n        helper(root.right , ans);\n    }\n    public IList<int> PreorderTraversal(TreeNode root) {\n        List<int> ans = new List<int>();\n        if(root == null)return ans;\n        helper(root , ans);\n        return ans;\n    }\n}\n```\n```python []\n# Definition for a binary tree node.\n# class TreeNode(object):\n#     def __init__(self, val=0, left=None, right=None):\n#         self.val = val\n#         self.left = left\n#         self.right = right\nclass Solution(object):\n    def helper(self , root , ans):\n        if root == None: return\n        ans.append(root.val)\n        self.helper(root.left , ans)\n        self.helper(root.right , ans)\n\n    def preorderTraversal(self, root):\n        """\n        :type root: TreeNode\n        :rtype: List[int]\n        """\n        ans = []\n        if root == None : return ans\n        self.helper(root , ans)\n        return ans\n    \n```\n```python3 []\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\nclass Solution:\n    def helper(self , root , ans):\n        if root == None: return\n        ans.append(root.val)\n        self.helper(root.left , ans)\n        self.helper(root.right , ans)\n    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n        ans = []\n        if root == None : return ans\n        self.helper(root , ans)\n        return ans\n```\n```ruby []\n# Definition for a binary tree node.\n# class TreeNode\n#     attr_accessor :val, :left, :right\n#     def initialize(val = 0, left = nil, right = nil)\n#         @val = val\n#         @left = left\n#         @right = right\n#     end\n# end\n# @param {TreeNode} root\n# @return {Integer[]}\ndef helper(root , ans)\n    if root == nil\n        return\n    end\n    ans.append(root.val)\n    helper(root.left , ans)\n    helper(root.right , ans)\nend\ndef preorder_traversal(root)\n    ans = []\n    if root == nil \n        return ans\n    end\n    helper(root , ans)\n    return ans\nend\n```\n# Dry Run \uD83D\uDE0E\n\n**1. Initialization:**\n- The preorderTraversal method is called with the root node of the binary tree.\n- Since the root is not null, an ArrayList<Integer> named ans is created to store the traversal result.\n- `ArrayList<Integer> ans = new ArrayList<>();`\n\n**2. First helper Call with Root Node (1):**\n\n- The helper method is called with the root node (which has the value 1) and the ans list.\n- Since root is not null, root.val (which is 1) is added to ans. Now, ans = [1]. `ans.add(root.val);`\n- The method then recursively calls itself for `root.left`, which is null, and immediately returns due to the base case.\n- Next, it calls itself for `root.right`, which is the node with the value 2.\n\n**3. Recursive helper Call with Node (2):**\n\n- For the node with the value 2, since it\'s not null, 2 is added to ans. Now, ans = [1, 2].\n- The method then recursively calls itself for `root.left` of node 2, which is the node with the value 3.\n\n**4. Recursive helper Call with Node (3):**\n\n- For the node with the value 3, since it\'s not null, 3 is added to ans. Now, ans = [1, 2, 3].\n- The method then attempts to call itself for both `root.left` and `root.right` of node 3, both of which are null. Both recursive calls immediately return due to the base case.\n\n**5. Backtracking and Completion:**\n\n- After processing node 3, the recursion unwinds back to node 2, and since both its left and right children (only left in this case) have been processed, it returns to the first call (node 1).\n- With both the right subtree of node 1 processed (there\'s no left subtree), the initial call to helper completes.\n\n**6. Return Result:**\n\n- The preorderTraversal method now returns the ans list, which contains the pre-order traversal result: [1, 2, 3].\n\n# Guys if the solution and explanation is helpful the upvote me.\n\n![Screenshot 2024-01-28 214252.png](https://assets.leetcode.com/users/images/f7f4d3e7-f0f8-411a-bae0-3a50a1d93df9_1707117135.0886676.png)\n\n\n\n\n\n\n\n\n\n
['Array', 'Tree', 'Binary Tree', 'Python', 'C++', 'Java', 'Python3', 'Ruby', 'JavaScript', 'C#']