Search in a Binary Search Tree

You are given the root of a binary search tree (BST) and an integer target

Find the node in the BST that the node’s value equals target and return the node. If such a node does not exist, return a node with value -1.

Class TreeNode:
    val (int)
    left (TreeNode)
    right (TreeNode)

Input Format:

First Parameter - TreeNode root

Second Parameter - number target

Output Format:

Return the TreeNode.

Example 1:

Input:
    root = [11 7 16 3 9]
    target = 7
Output:
    [7 3 9]

Example 2:

Input:
    root = [11 7 16 3 9]
    target = 5
Output:
     [-1]

Constraints:

• The number of nodes in this tree is in the range of [1,5 *10³]
• 1 <= node.val <= 10⁷
• root is a binary search tree.
• 1 <= target <= 10⁷
• Expected Time Complexity: O(h), h is the height of the binary search tree.
• Expected Space Complexity: O(h), h is the height of the binary search tree.