C++ || Recursion || Full Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \n- Using Recursive Approach.\n\n# Approach\n- A binary tree is a recursive object where 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n- Using Recursive Approach.\n\n# Approach\n- A binary tree is a recursive object where we have three essential components\n     - Root node: The topmost node of a binary tree.\n\n    - Left-subtree: A smaller binary tree connected via the left pointer of root node.\n\n    - Right-subtree: A smaller binary tree connected via the right pointer of root node.\n\n- So traversing a binary tree requires traversal of each component Processing root node, traversing the left subtreeand traversing the right subtree.\n\n![image.png](https://assets.leetcode.com/users/images/cad94ad3-9f35-497f-ac31-166c06c6d627_1673231417.744738.png)\n\n## Recursive preorder traversal of binary tree \n- In recursive preorder traversal, we first process the root node, then process all nodes in the left subtree, and finally, we process all nodes in the right subtree Suppose we use a function precrder(root) with root as an input parameter.\n\n### Steps of recursive preorder implementation\n\n- First, store data stored in the root node i.e process(root->value) in vector\n- Then we recursively traverse and process each node in the left subtree by calling the same function with root->left as input parameter i.e preorder(root->left).\n- Then we recursively traverse and process each node in the right subtree by calling the same function with rout->right as input parameter ie preorder(root->right). \n- Base case: recursion will terminate and backtrack when it reaches the bottommost end of binary tree, i.e root==NULL\n\n![image.png](https://assets.leetcode.com/users/images/a4ee446e-7b0d-41a2-bac8-365b4398b3db_1673231891.0546484.png)\n![image.png](https://assets.leetcode.com/users/images/41544952-4e5f-4f7d-8861-273e3e7b0ce5_1673231902.5866964.png)\n\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\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 preorder(TreeNode* root, vector<int> &a)\n        {\n            // Base Case\n            if(root==NULL)\n                return;\n\n            a.push_back(root->val);// store in vector\n            preorder(root->left,a);// recursion for left sub tree\n            preorder(root->right,a);// recursion for right sub tree\n        }\n    vector<int> preorderTraversal(TreeNode* root) {\n       vector<int> a;\n        preorder(root,a);\n        return a;\n    }\n};\n```
['Tree', 'Recursion', 'C++']