[LeetCode]#700. Search in a Binary Search Tree

Environment: Python 3.8

Key technique: TreeNode

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3
And the value to search: 2

You should return this subtree:

2     
     / \   
    1   3

Analysis:

1. if root is nothing, return None.

2.if root.val is equal to val, return root.

3. if root.val >val, root=root.left

4.if root.val <val, root=root.right

Solution:

class Solution:
    def searchBST(self, root, val):
        if root is None:
            return None
        
        while root:
            if root.val == val:
                return root
            elif root.val > val:
                root = root.left
            else:
                root = root.right
                
        return root

Submissions:

Reference:

https://leetcode.com/problems/search-in-a-binary-search-tree/discuss/997676/Python