🌳 Easy-to-Understand recursion Solution || Java || Well explained || Beats 100% 💯🌳
---\n# \u2B06\uFE0FPlease upvote if you find it helpful\u2B06\uFE0F\n---\n## Intuition \uD83D\uDCA1\nThe problem requires us to search for a node in a Binary Se
---\n# \u2B06\uFE0FPlease upvote if you find it helpful\u2B06\uFE0F\n---\n## Intuition \uD83D\uDCA1\nThe problem requires us to search for a node in a Binary Search Tree (BST) that matches a given value `val`. Given the properties of a BST, where the left child node is always smaller and the right child node is always larger than the root node, we can take advantage of this ordering to efficiently search for the target value.\n\n## Approach \uD83D\uDE80\n1. **Base Condition:**\n- Start by checking if the current `root` is `null` or if the current `root.val` is equal to the target `val`. If either is true, return the `root`.\n- If `root` is `null`, it means we\'ve reached a leaf node without finding the target value, so we return `null`.\n- If `root.val` is equal to `val`, we\'ve found the target node, so we return the current `root`.\n\n2. **Recursive Search:**\n- If the current `root.val` is greater than `val`, we search in the left subtree because the target value must be smaller.\n- If the current `root.val` is less than `val`, we search in the right subtree because the target value must be larger.\n\n3. **Return the Result:**\n- After the recursive search, if the target value exists in the tree, the corresponding subtree root node is returned. If the value does not exist, `null` is returned.\n\n## Complexity \u23F1\uFE0F\n- **Time Complexity:**  \nThe time complexity is $$O(h)$$, where `h` is the height of the tree. In the worst case, the time complexity is $$O(n)$$, where `n` is the number of nodes (in the case of a completely unbalanced tree). However, in a balanced BST, the time complexity is typically $$O(\\log n)$$.\n\n- **Space Complexity:**  \nThe space complexity is $$O(h)$$ due to the recursive stack space, where `h` is the height of the tree. This could be $$O(n)$$ in the worst case, or $$O(\\log n)$$ in a balanced tree.\n\n## Code \uD83D\uDCBB\n\n---\n\n```java []\n/**\n * Definition for a binary tree node.\n * public class TreeNode {\n *     int val;\n *     TreeNode left;\n *     TreeNode right;\n *     TreeNode() {}\n *     TreeNode(int val) { this.val = val; }\n *     TreeNode(int val, TreeNode left, TreeNode right) {\n *         this.val = val;\n *         this.left = left;\n *         this.right = right;\n *     }\n * }\n */\nclass Solution {\n    public TreeNode searchBST(TreeNode root, int val) {\n        //base condition\n        if(root == null || root.val == val)return root;\n       \n        // Travel in the tree;\n        if(root.val > val){\n            root = searchBST(root.left,val);\n        }else{\n            root = searchBST(root.right,val);\n        }\n\n        // If the value doesn\'t exist return null\n        return root;\n    }\n}\n```
['Binary Search Tree', 'Recursion', 'Java']