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.

&nbsp;
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: []


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 5000].
	1 &lt;= Node.val &lt;= 107
	root is a binary search tree.
	1 &lt;= val &lt;= 107


# 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
class Solution:
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        def search(root):
            if not root:return None
            if root.val==val:
                return root
            elif root.val<val:
                ans=search(root.right)
                if ans:
                    return ans
                return None
            else:
                ans=search(root.left)
                if ans:
                    return ans
                return None
        return search(root)
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return root;
        if (root.val == val) {
            return root;
        } else {
            return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
        }
    }
}
// Recursive
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int& val) {
        if(root==NULL) return NULL;
        if(root->val==val) return root;
        if(root->val>val) return searchBST(root->left,val);
        return searchBST(root->right,val);
    }
};

// Iterative
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        while(root){
            if(root->val==val) return root;
            root=root->val>val?root->left:root->right;
        }
        return NULL;
    }
};
//====== Recursion ======
var searchBST = function(root, val) {
    if (!root) return null;
    if (root.val===val) return root;
    return searchBST(root.left, val) || searchBST(root.right, val)
}

//====== Iteration ======
var searchBST = function(root, val) {
    if (!root) return null;
    let node = root

    while (node) {
        if (node.val === val) return node;
        else node = node.val > val ? node.left : node.right
    }

    return node
}
Search in a Binary Search Tree