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:
[1, 5000]
.1 <= Node.val <= 107
root
is a binary search tree.1 <= val <= 107
Source
# 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
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)
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