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 integerval
.
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, returnnull
.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
What do we know?
- We have a Binary Search Tree and we have to search for a value
- 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:
- 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. - So firstly, we're going to do this recursively. Meaning, we need to check every
node
for every possible outcome. - Firstly we ask, is this
node
a leafnode
? In this case, we reached the end of the list never finding what we looked for. - 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 thenode
. - 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. - 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
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);
}
};
Top comments (0)