Easiest Solution using Recursion
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem asks to search for a value in a Binary Search Tree (BST) and return the cor
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem asks to search for a value in a Binary Search Tree (BST) and return the corresponding node if the value exists. In a BST, the left child is always smaller than the root, and the right child is always larger. This property can be leveraged to traverse the tree efficiently.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Start from the root node.\n2. If the current node\'s value equals the target value, return the node.\n3. If the current node\'s value is greater than the target value, search in the left subtree (as the target must be smaller).\n4. If the current node\'s value is less than the target value, search in the right subtree (as the target must be larger).\n5. If you reach a NULL node (leaf node), return NULL, indicating the value doesn\'t exist in the tree.\n\nThis recursive approach leverages the BST properties, reducing unnecessary searches.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nThe height of the tree, h, determines the maximum number of recursive calls. In the worst case, h can be the number of nodes in the tree (for a skewed tree), leading to a time complexity of \uD835\uDC42(\uD835\uDC5B), where n is the number of nodes. For a balanced BST, the height is O(logn).\n- Space complexity\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe space complexity is determined by the recursion stack. In the worst case (for a skewed tree), the depth of the recursion stack is equal to the height of the tree, which can be O(n). For a balanced tree, it will be O(logn).\n# Code\n```cpp []\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        }\n        if (root->val>val){\n           return  searchBST(root->left,val);\n        }\n        else{\n           return  searchBST(root->right,val);\n        }\n        // return root;\n    }\n};\n```
['Tree', 'Binary Search Tree', 'Binary Tree', 'C++']