Search in a Binary Search Tree

Problem

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.

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

Solution

The problem Search in a Binary Search Tree can be solved by searching for the given value in the binary search tree. Space complexity can be optimized by using iteration over recursion.

Implementation

static const int fast_io = []()
{
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    return 0;
}();

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution
{
  public:
    TreeNode *searchBST(TreeNode *root, int val)
    {
        while (root != NULL)
        {
            if (val < root->val)
                root = root->left;
            else if (val > root->val)
                root = root->right;
            else
                break;
        }

        return root;
    }
};