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(logn)
Space complexity: O(1)

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

        return iter;
    }
};