Search in a Binary Search Tree (Leet Code-700)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 226. This is a Leet code problem named Search in a Binary Search Tree. We will solve it using python and it is the best space and time-optimized solution.

Question of Search in a Binary Search Tree

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

Example 1

Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]

Example 2

Input: root = [4,2,7,1,3], val = 5
Output: []

Constraints

The number of nodes in the tree is in the range [1, 5000].
1 <= Node.val <= 10⁷
root is a binary search tree.
1 <= val <= 10⁷

Recursive Approach to solve Search in a Binary Search Treeee

To solve this problem we will recursively call the Binary Search Tree function. We compare the node’s value to the value we want to search. If the root value is greater than the node value then we traverse to the left side otherwise we traverse to the right side.

Algorithm

This method performs the following steps for a given input binary search tree:

Check for the base case.
Check if the root value is equal to the given value.
If yes then return the root
If the node value is greater than the given value then traverse left.
If the node value is less than the given value then traverse right.
End if

Python Code for Search in a Binary Search Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
            
        def helper(root,val):
            #base case
            if(not root):
                #if root doen not exists then return None
                return root
            
            #check if root value is equal to given value
            if(root.val == val):
                #if yes then return root
                return root
            
            if(root.val>val):
                #if node value is greater than given value then traverse left
                return  helper(root.left,val)
            elif(root.val<val):
                #if node value is less than given value then traverse right
                return helper(root.right,val)
            else:
                return None
        
        
        return helper(root,val)