Day 1: Search in a Binary Search Tree
Leetcode 75-day challenge
After seeing various 75-day challenges all over the internet, such as the 75-day challenge to lose weight or the 75-day challenge to learn something new, I finally decided to join in and started my own 75-day LeetCode challenge. For the first problem, I intentionally chose an easy one to build my confidence and keep myself motivated to continue.
So, the the problem I chose to start with is: Search in a Binary Search Tree
Before I start explaining the solution to this problem, I assume that the reader of this blog has a basic understanding of how Binary Search Trees (BST) work. If not, you can watch my YouTube video on the topic here:
Let’s start:
The problem states that given the BST root node and a value we need to find the node and return the subtree.
For eg:
We need to locate node 2 and return its subtree, which consists of nodes 2, 1, and 3. Essentially, we’re returning the left subtree.
So, the code will look something like this:
The searchBST function takes two arguments: the first is the root node of the BST, and the second is the value we need to find in the BST.
The if statement checks if the root is null. If it is null, there's no need to execute further code, so we return null.
After the if statement, we assign the root node to a temporary variable. Then, we enter a while loop, where we continuously traverse the BST based on the comparison of the target value with the value of the current node. If the value is less than temp.val, we move to the left side of the tree; if it's greater, we move to the right. If we find the value, we return the temporary variable, which holds the node with the desired value and its subtree. If the value is not found, we return null.
So, in conclusion, we just need to compare the value with temp.val and move left and right according to it.
You can check out the github gist here.
I hope I was able to explain the solution and it’ll help and motivate you to start the challenge as well.
