Solution Developed In:

The Question

For this article we will be covering Leetcode's '700. 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:

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
2. Binary Search Trees
3. Depth First Search Recursive
4. 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 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 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
• 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

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);
    }
};