How To Find A Target Node in A Binary Search Tree

The Binary Search Tree is a staple of the coding interview. I will review how to solve this problem in javascript. “Given a Binary Search Tree and a Target element, see if the Tree includes the Target element”:

We will be using a helper function that also takes in the start and stop nodes that we will be traversing. Due to the nature of the Binary Search Tree, we can conclude that all values on the left will be less than the root node, and all values on tehr gith will be greater than the root node.

First, let’s create some default values for our start and stop. We’ll start at 0, and stop at tree.length -1. That will give us the first and last index of our tree.

Next, we will calculate the midpoint of our tree. This would also be considered the root. We’ll do so by adding the following to our function:

Next, we’ll create our switch case. We will be solving this problem recursively, so let’s put forth a couple of situations where we know that we will be returning true or false based on our element in the search. These include if the midPoint we have calculated is equal to 0, or if it’s equal to the target element.

Now, if our target is too high or two low, we have already addressed the two base cases and can go into using our function recursively. In which case, if the target element is less than the tree[midPoint]…

Or if it’s greater, we know we will only be traversing the side of the tree greater than the midPoint. So let’s write a line of code for that scenario as well.

And viola! This algorithm works with O(log N) time