700. Search in a Binary Search Tree

1. Description

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.

2. Example

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: []

3. Constraints

• The number of nodes in the tree is in the range [1, 5000].
• 1 <= Node.val <= $10^7$
• root is a binary search tree.
• 1 <= val <= $10^7$

4. Solutions

Binary Search Tree

n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    TreeNode *searchBST(TreeNode *root, int val) {
        while (root != nullptr && root->val != val) {
            root = root->val < val ? root->right : root->left;
        }

        return root;
    }
};