Best O(h) Solution
Approach 1\nRecursive Solution\n\n# Complexity\n- Time complexity:\nO(h) --> h is height of the BST\n\n- Space complexity:\nO(h) --> h is height of the BST\n\n#
# Approach 1\nRecursive Solution\n\n# Complexity\n- Time complexity:\n$$O(h)$$ --> h is height of the BST\n\n- Space complexity:\n$$O(h)$$ --> h is height of the BST\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->left, val);\n        else\n            return searchBST(root->right, val);        \n    }\n};\n```\n\n# Approach 2\nIterative Solution\n\n# Complexity\n- Time complexity:\n$$O(h)$$ --> h is height of the BST\n\n- Space complexity:\n$$O(1)$$ \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        while (root != NULL && root->val != val) {\n            if (root->val > val)\n                root = root->left;\n            else\n                root = root->right;    \n        }\n        return root;        \n    }\n};\n```
['C++']