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 <= 107
root is a binary search tree.
1 <= val <= 107
Solutions
Solution 1: Recursion
We check if the current node is null or if the current node's value equals the target value. If so, we return the current node.
Otherwise, if the current node's value is greater than the target value, we recursively search the left subtree; otherwise, we recursively search the right subtree.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the number of nodes in the binary tree.
1 2 3 4 5 6 7 8 9101112131415
# 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 = rightclassSolution:defsearchBST(self,root:Optional[TreeNode],val:int)->Optional[TreeNode]:ifrootisNoneorroot.val==val:returnrootreturn(self.searchBST(root.left,val)ifroot.val>valelseself.searchBST(root.right,val))
1 2 3 4 5 6 7 8 91011121314151617181920212223
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */classSolution{publicTreeNodesearchBST(TreeNoderoot,intval){if(root==null||root.val==val){returnroot;}returnroot.val>val?searchBST(root.left,val):searchBST(root.right,val);}}
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */funcsearchBST(root*TreeNode,valint)*TreeNode{ifroot==nil||root.Val==val{returnroot}ifroot.Val>val{returnsearchBST(root.Left,val)}returnsearchBST(root.Right,val)}