C++ - EASY - 2 Solutions - Recursive & Iterative
Intuition\nRecursively traversing the tree based on BST Property & comparing data of nodes & value we have to search. \n Describe your first thoughts on how to 
# Intuition\nRecursively traversing the tree based on BST Property & comparing data of nodes & value we have to search. \n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach - *Recursive*\n<!-- Describe your approach to solving the problem. -->\n- **2 Base Cases**\n    - *if root is NULL, we return NULL ;* \n    - *if data of root matches to value to be searched, we return the node;*\n- **Recursive Traversal Statements based on comparison of node\'s data & the value to be searched and the BST Property**\n    - *if data of node is greater than value, we search in the left subtree & OMIT right subtree*\n    - *Else, we search in the right subtree & OMIT the left subtree.*\n\n# Complexity\n- Time complexity:$$O(log 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```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    TreeNode* searchBST(TreeNode* root, int val) {\n        // base case \n        // if element not found or if element found \n        if (root == NULL)\n        {\n            return NULL ; \n        }\n\n        if (root -> val == val)\n        {\n            return root ; \n        }\n\n        // return statments mandatory in recursion because return type non NULL here\n        // left part traverse\n        if (root -> val > val)\n        {\n            return searchBST(root -> left, val) ;\n        }\n\n        // right part traverse \n        else    \n        {\n            return searchBST(root -> right, val) ; \n        }\n    }\n};\n```\n---\n# *OPTIMIZED SOLUTION* \n# Intuition\nWe know, whenever we reach NULL it means that the element is absent in the tree. Because in a BST, an element can not exist anywhere else.\nTherefore, we don\'t necessarily need to go back to the previous node & traverse to some other subtree.\nSo, this can be solved ITERATIVELY without RECURSION\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach - *Iterative*\n- Create a `temp` node & make it equal to root; \n- Now, traverse **till temp is NOT EQUAL to NULL**\n- While traversing \n    - Compare *temp\'s data & the val* which we have to find.\n    - ***Move to left or right child of temp based on the comparison using the BST Property***\n> **BST Property**\n*Left Child Value < Node Value \nRight Child Value > Node Value*>\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:$$O(log N)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\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    TreeNode* searchBST(TreeNode* root, int val) {\n        // Solving Iteratively \n        // with Constant O(1) Space Complexity \n        // Optimised Solution \n\n        TreeNode *temp = root ; \n\n        while(temp != NULL)\n        {\n            if (temp -> val == val)\n            {\n                return temp ; \n            }\n\n            if (temp -> val > val)\n            {\n                temp = temp -> left; \n            }\n\n            else\n            {\n                temp = temp -> right ; \n            }\n        }\n        return NULL ;  \n    }\n};\n```\n![815a317f-9cdf-46e2-a397-af8869dafa2e_1673498197.3721023.png](https://assets.leetcode.com/users/images/587b327a-0c8a-4f25-8268-66087409fe88_1687065985.4967413.png)\n
['Tree', 'Binary Search Tree', 'Binary Tree', 'C++']