> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/binary-search-tree/search-in-a-binary-search-tree.md).

# 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:**

![](https://assets.leetcode.com/uploads/2021/01/12/tree1.jpg)

```
Input: root = [4,2,7,1,3], val = 2
Output: [2,1,3]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/01/12/tree2.jpg)

```
Input: root = [4,2,7,1,3], val = 5
Output: []
```

## **Solution Iteratively:-**

```cpp
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:-** 

```cpp
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).**