> 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/insert-into-a-binary-search-tree.md).

# 3.Insert into a Binary Search Tree

You are given the `root` node of a binary search tree (BST) and a `value` to insert into the tree. Return *the root node of the BST after the insertion*. It is **guaranteed** that the new value does not exist in the original BST.

**Notice** that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return **any of them**.

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/10/05/insertbst.jpg)

```
Input: root = [4,2,7,1,3], val = 5
Output: [4,2,7,1,3,5]
Explanation: Another accepted tree is:

```

**Example 2:**

```
Input: root = [40,20,60,10,30,50,70], val = 25
Output: [40,20,60,10,30,50,70,null,null,25]
```

**Example 3:**

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

### Approach:

* Find the element if it is found then return
* Else if the element is not found, find the position where the element should be inserted. 

### Iterative Solution : 

```cpp
class Solution
{
public:
    TreeNode *insertIntoBST(TreeNode *root, int val)
    {
        if(root == NULL){
              TreeNode *temp = new TreeNode;
              temp->val = val;
              temp->left = NULL;
              temp->right = NULL;
              root = temp;
              return root;
        }
        
        TreeNode *p = root;
        TreeNode *q = NULL;

        while (p != NULL)
        {
            q = p;
            if (p->val == val)
            {
               return root;
            }
            else if (p->val > val)
            {
                p = p->left;
            }
            else
            {
                p = p->right;
            }
        }

        TreeNode *temp = new TreeNode;
        temp->val = val;
        temp->left = NULL;
        temp->right = NULL;
        if (q->val > val)
        {
            q->left = temp;
        }
        else
        {
            q->right = temp;
        }
        return root;
    }
};

```

**Time complexity: O(log n)**