700. Search in a Binary Search Tree | LeetCode | Python | Solution

Click here to see the problem in LeetCode. Read the description carefully.

This one is a pretty easy problem for you if you know how to search on Binary Search Tree (BST).

First, we will be given a Binary Search Tree and a value for search. We have to search for the given value in the given tree and have to return the subtree rooted with that node, where the node value is equal to the given value. If the given value doesn’t exist in the tree, we have to return NULL.

Coding Part

A Binary Search Tree is also a Binary Tree. But we all know that in BST, the left subtree or left node has to be less than the parent node. And the right subtree or right node has to be greater than the parent node.

So, will be given the root of a BST. So that we can traverse through the tree. According to the BST rule, the value of all left nodes will be less than the root, and the value of all left nodes will be greater than the root. It makes the search easier for us.

Suppose our given value is greater than the current node value; In that case, there is no need to search on the left side of the node. On the other hand, if the value is smaller than the current node, we will look into the left side nodes, and so on. We will continue the search until we found the value.

Let’s see BST from the LeetCode example.

        4
       / \
      2   7
     / \
    1   3

In the given BST, assume that we are looking for the value ‘2’. First, our root node value is ‘4’.

That’s why we check this node value with our given value. In this case, ‘2’ is smaller than ‘4’. So, we have to search on the left side of this node, and the left node of the ‘4’ is ‘2’. Let’s check this node with the given value. This time the given value is equal to the current node value. Arriving at this place, we have got our desired node.

If we found our desired node, we will return the node, not the node value. If the node has any other child or subtree, we can easily found them. We don’t need to worry about those child nodes or subtree. We have to return that node, nothing else.
If the node doesn’t exist, we will return NULL.

We can solve this problem iteratively and recursively. Let’s see both of the solutions. Code can explain better than me.

Iterative Solution

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        
        while root:
            
            if val < root.val:
                root = root.left
            elif val > root.val:
                root = root.right
            else:
                return root

Recursive Solution

class Solution:
    def searchBST(self, root: TreeNode, val: int) -> TreeNode:
        
        if not root:
            return None
        
        if root.val == val:
            return root
        
        if val < root.val:
            return self.searchBST(root.left, val)
        if val > root.val:
            return self.searchBST(root.right, val)

These are the solution to this problem. I hope you got the idea. Try to understand the solution with a simple example first.

Happy Learning 🙂
Happy Coding 🙂

Tags: Binary SearchBinary TreeLeetCodeRecursionTree