Search In BST using Recursion 🔥🔥
\n# Approach\n Describe your approach to solving the problem. \n- Simply this problem can be solved using recursion .\n- First we will check the root element th
\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Simply this problem can be solved using recursion .\n- First we will check the root element then we will go to the left or right subtree according to the search element if search element is greater than root than go on right if it\'s not then go on left.\n# Using Recursion\n- Step 1: Check if the current Node is Null. If it is null means target value not found and return NULL. `if(root==NULL) \n            return NULL`\n-  Step 2: If the the Searched value matches the current Node data just return the data `if(root->val==val)\n            return root;`\n-  Step 3: If the searched value is smaller than root element than search on left part of a tree recursively. `if(root->val>val)\n            return searchBST(root->left,val);`\n- Step 4: If the Searched value is greater then search on right part recursively. `if(root->val<val)\n            return searchBST(root->right,val);`\n\n\n# Algorithm\n    If root == NULL \n        return NULL;\n    If number == root->data \n        return root->data;\n    If number < root->data \n        return search(root->left)\n    If number > root->data \n        return search(root->right)\n# Complexity\n- Time complexity:$$O(log n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\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    TreeNode* searchBST(TreeNode* root, int val) {\n        if(root==NULL) \n            return NULL;\n        if(root->val==val)\n            return root;\n        if(root->val<val)\n            return searchBST(root->right,val);\n        return searchBST(root->left,val);\n\n    }\n};\n```
['Recursion', 'C++']