Notebook

700. 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 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⁷

Source

In [1]:

# 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

Code

In [ ]:

def search_bst(root, val):
    """Recursive approach."""
    if not root:
        return None
    if root.val == val:
        return root
    if val < root.val:
        return search_bst(root.left, val)
    if val > root.val:
        return search_bst(root.right, val)

In [ ]:

def search_bst(root, val):
    """Alternative version of above solution."""
    if root and val < root.val:
        return search_bst(root.left, val)
    if root and val > root.val:
        return search_bst(root.right, val)
    return root