2.Search in a Binary Search Tree

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.

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

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

Solution Iteratively:-

class Solution
{
public:
    TreeNode *searchBST(TreeNode *root, int val)
    {

        TreeNode *t = root;
        
        while(t!=NULL){
            if(t->val == val){
                break;
            }
            else if(t->val > val){
                t = t->left;
            }
            else{
                t = t->right;
            }
        }
        
        return t;
     
    }
};

Solution Recursively:-

class Solution
{
public:
    TreeNode *searchBST(TreeNode *root, int val)
    {

        if (root == NULL || root->val == val)
        {
            return root;
        }
        else if (root->val > val)
        {
            return searchBST(root->left, val);
        }
        else
        {
            return searchBST(root->right, val);
        }
    }
};

Time Complexity of searching in a BST

Maximum number of comparisons is h i.e height of binary search tree So time complexity O(h) i.e O(log n).