700. Search in a Binary Search Tree 🚀
Tags: javascript, beginners, leetcode, tutorial
Published: 2022-05-18 19:46:19

***
### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[700. Search in a Binary Search Tree](https://leetcode.com/problems/search-in-a-binary-search-tree/)' question. 

Question:

> You are given the `root` of a **binary search tree** (BST) and an integer `val`.
> Find the **node** in the BST that the **node**'s value equals val and return the subtree rooted with
> that **node**. If such a **node** does not exist, return `null`.
> 
Example:

>![Example](https://assets.leetcode.com/uploads/2021/01/12/tree1.jpg)

```
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
```

## Explaining The Question
This Question is rated **Easy**. Which is for the most part accurate. But this is **ONLY** easy if you have a basic understanding of **Binary Search Trees**. If you don't, then you will be having a **Bad Day** with this question.

What we're being asked is to locate a number in a BST. If the number is not in the BST, then we return `null`. If the number is in the BST, then we return the subtree rooted with that number.
***

##  Recommended Knowledge
1. [Binary Trees](https://en.wikipedia.org/wiki/Binary_tree)
2. [Binary Search Trees](https://en.wikipedia.org/wiki/Binary_search_tree)
3. [Depth First Search Recursive](https://en.wikipedia.org/wiki/Depth-first_search#Recursive_algorithm)
4. [Divide and Conquer](https://en.wikipedia.org/wiki/Divide_and_conquer)

## What do we know?
1. We have a Binary Search Tree and we have to search for a value
2. We can do this in ***O(log n)*** by using the **Binary Search Tree**'s properties. Which allows us to search with [Divide and Conquer](https://en.wikipedia.org/wiki/Divide_and_conquer) algorithms.

## How we're going to do it:
1. 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. 
2. So firstly, we're going to do this recursively. Meaning, we need to check every `node` for every possible outcome. 
3. 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.
4. 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`.
5. 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.
6. We repeat this until we reach the end of the list or what we came looking for.

## Big O Notation:
* Time Complexity:   *O(**log n**)* | Where ***n*** is the number of `node`s 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
* Space Complexity: *O(**1**)* | As we never allocate any extra space. 

## Leetcode Results:

See Submission Link: 

* Runtime: 72 ms, faster than ***97.71%*** of JavaScript online submissions for Search in a Binary Search Tree

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/680109112/)


***

# The Solution
```
var searchBST = function (root, val) {
    
	// We have reached a leaf node
	// This mean's we never found the
	// node we was looking for.
	if (!root) {
		return null;
	}

	// We found the node we're looking for
	// Return it.
	if (root.val === val) {
		return root;
	}

	// The 2 parts below only make sense if you understand
	// Binary Search Trees. It helps if you understand divide and conquer algorithms.
	// Like Binary search.

	// So we know the value we're looking for
	// if greater than the current node, thus
	// the node we're looking for is somewhere on the right tree
	if (val > root.val) {
		return searchBST(root.right, val);
	}

	// So the value we're searching for is less than the current node
	// which means the node we're looking for exists somewhere on
	// the left side.
	if (val < root.val) {
		return searchBST(root.left, val);
	}
};

```