Skip to main content

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.

Solution Approach​

Expected Time complexity: O(n)O(n)

Click - to see solution code
class Solution {
   public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if (root == NULL) return root;
        if (root->val == val) return root;
        if (root->val > val)
            root = root->left;
        else
            root = root->right;
        return searchBST(root, val);
    }
};