[LeetCode] 700. Search in a Binary Search Tree

1. Question

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 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: []
 

2. Thoughts

Use Binary Tree characteristic
if bigger, go right
smaller, go left
same, return

3. Tips learned

4. My solution

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root

        while True:
            if not node or val == node.val:
                return node
            if val > node.val:
                node = node.right
            else:
                node = node.left

36/36 cases passed (68 ms)
Your runtime beats 75.32 % of python3 submissions
Your memory usage beats 24.49 % of python3 submissions (18.6 MB)

5. AI Solution and Improvements

Your solution for finding a node in a Binary Search Tree (BST) with a given value is efficient and leverages the properties of a BST effectively. The iterative approach makes it straightforward and avoids the stack space overhead of recursion. However, the use of an infinite loop (while True) can be replaced with a condition that directly reflects the termination criteria of the loop, making the code slightly more readable and explicitly safe.

Here's a slightly optimized version of your code:

class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        node = root

        while node:
            if val == node.val:
                return node
            elif val < node.val:
                node = node.left
            else:
                node = node.right
        
        return None  # Explicitly return None if the value is not found

In this revised version:

• The while loop condition is directly tied to the existence of the current node, which is more intuitive than while True. It stops when node becomes None, which happens when you've reached a leaf node's child or if the initial root is None.
• The return None at the end is explicit, making it clear that the function returns None if the value is not found in the BST. This enhances code readability and understanding, although it's functionally the same as your original code since a Python function returns None by default if no return statement is executed.