⭐ JS | Simple & Explained | Optimal Solution
700. Search in a Binary Search Tree \uD83D\uDE80\n\n### Solution Developed In:\n\n\n ### Index:\n1. <a href="#explaining-the-question">Explaining the Question</
# 700. Search in a Binary Search Tree \uD83D\uDE80\n***\n### Solution Developed In:\n![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)\n\n<!-- ### Index:\n1. [Explaining the Question](#explaining-the-question)\n2. [Recommended Knowledge](#what-do-we-know)\n3. [What do we know](#recommended-knowledge)\n4. [Solution Explanation](#how-were-going-to-do-it)\n5. [Big *O* Notation](#big-o-notation)\n6. [Leetcode Results](#leetcode-results)\n7. [Solution](#the-solution) -->\n\n## Explaining The Question\nSo we\'re given a number and must locate it in the tree.\nWe can now perform our standard DFS or BFS algos, but this is a binary search tree. That is, we can use a divide and conquer algorithm to find exactly what we are looking for by halving the size of the tree with each node we traverse. Super fast.\n\n\nThink of it like using Binary search on a sorted array.\n\nA Binary Search Tree is a tree that has been sorted in such a way that we can move through it at breakneck speed. At each node, the value to the left is less than the current value, and the value to the right is greater than the current value. That\'s it.\n\n***\n\n##  Recommended Knowledge\n1. Binary Trees\n2. Binary Search Trees\n3. Recursive Searching in a tree\n4. How to traverse a Binary Search Tree\n\n## What do we know?\n1. We have a Binary Search Tree and we have to search for a value\n2. We can do this in ***O(log n)***\n\n## How we\'re going to do it:\n1. We\'re going to go to every node and ask if the given value is greater than or less than the value we need to find. \n2. So firstly, we\'re going to do this recursively. Meaning, we need to check every node for every possible outcome. \n3. Firstly we ask, is this node a ***leaf node*** ? In this case, we reached the end of the list never finding what we looked for.\n4. We then ask, \'Is the current node the one we have been searching for?\' we do this by comparing values. If they\'re the same, we found it so we return the node.\n5. Now we need to know where to go next if we never found it, do we go left or right? If the current value is greater than what we\'re searching for, we go left as we know the left values are always lesser than the current value and thus our value will be on the left side. The same logic applies to the right node, where if the current value is lesser than the value we\'re looking for, we go right as we know that\'s where the larger number are.\n6. We repeat this until we reach the end of the list or what we came looking for.\n\n## Big O Notation:\n* Time Complexity:   *O(**log n**)* | Where ***n*** is the number of nodes the tree has and ***log*** because we\'re half-ing the search tree on every move. It\'s logarithmic. We\'re using a ***divide and conquer*** algorithm\n* Space Complexity: *O(**1**)* | As we never allocate any extra space or have the need to bubble up in the call stack.\n\n## Leetcode Results:\n\nSee Submission Link: \n\n* Runtime: 72 ms, faster than ***97.71%*** of JavaScript online submissions for Search in a Binary Search Tree\n\n[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/680109112/)\n\n\n***\n\n# The Solution\n```\nvar searchBST = function (root, val) {\n    \n\t// We have reached a leaf node\n\t// This mean\'s we never found the\n\t// node we was looking for.\n\tif (!root) {\n\t\treturn null;\n\t}\n\n\t// We found the node we\'re looking for\n\t// Return it.\n\tif (root.val === val) {\n\t\treturn root;\n\t}\n\n\t// The 2 parts below only make sense if you understand\n\t// Binary Search Trees. It helps if you understand divide and conquer algorithms.\n\t// Like Binary search.\n\n\t// So we know the value we\'re looking for\n\t// if greater than the current node, thus\n\t// the node we\'re looking for is somewhere on the right tree\n\tif (val > root.val) {\n\t\treturn searchBST(root.right, val);\n\t}\n\n\t// So the value we\'re searching for is less than the current node\n\t// which means the node we\'re looking for exists somewhere on\n\t// the left side.\n\tif (val < root.val) {\n\t\treturn searchBST(root.left, val);\n\t}\n};\n\n```
['Binary Search Tree', 'Recursion', 'JavaScript']