Search in a Binary Search Tree

Question (LC.700)

Given the root of a BST and a target value, find the node with the corresponding value.

Example

I: Given the root 4, target value is 2 
        4
       / \
      2   7
     / \
    1   3

O: 
      2     
     / \   
    1   3

Analysis

Searching a balanced BST is fast. O(logn) time.

Code

def searchBST(self, root: TreeNode, val: int) -> TreeNode:
    
    if root is None:
        return None 
    
    if root.val == val:
        return root 
    
    if val >= root.val:
        return self.searchBST(root.right, val)
    else:
        return self.searchBST(root.left, val)