# মডিউল ২১-৫ঃ Insert in BST

এই module এ আমরা দেখবো একটা BST তে কিভাবে value insert করতে হয়। আমরা এর আগে জেনেছি BST তে Value গুলো এটা Format Maintain করে সাজানো থাকে। Left এ ছোট আর Right এ বড় value থাকে।

<figure><img src="/files/2aUjYf3EM8iTPUYyZDFX" alt=""><figcaption></figcaption></figure>

এখানে দেখতে পারছি 12 যদি আমাদের insert করতে হয় তাহলে এইভাবে 20 -> 10 -> 15 -> এর পর 12 বসাতে হবে। insertion এর বেলায় কয়টা condition হতে পারে।

১) root এ কোনো value না থাকতে পারে সেক্ষেত্রে root এ value insert করতে হবে।

২) আবার একেবারে null এ গিয়ে proper position পাওয়া যায় সেক্ষেত্রে null এর আগের value এর child হিসেবে value insert করতে হবে।

এবার code দিয়ে বুঝা যাক।

```cpp
void insert(Node *&root, int x)

{
// root এ value না থাকলে root এ new node বানাবো
    if (root == NULL)
    {
        root = new Node(x);
        return;
    }
//left এ value না থাকলে root এ new node বানাবো নাহলে 
    if (x < root->val)
    {
        if (root->left == NULL)
        {
            root->left = new Node(x);
        }

        else
        {
            insert(root->left, x);
        }
    }

//right এ value না থাকলে root এ new node বানাবো
    else
    {
        if (root->right == NULL)
        {
            root->right = new Node(x);
        }
        else
        {
            insert(root->right, x);
        }
    }
}
```

**BST insert operation time complexity:** O(N)<br>

**Full code:**

```cpp
#include <bits/stdc++.h>
using namespace std;
class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};
Node *input_tree()
{
    int val;
    cin >> val;
    Node *root;
    if (val == -1)
        root = NULL;
    else
        root = new Node(val);
    queue<Node *> q;
    if (root)
        q.push(root);
    while (!q.empty())
    {
        // 1. ber kore ano
        Node *p = q.front();
        q.pop();

        // 2. jabotiyo ja kaj ache
        int l, r;
        cin >> l >> r;
        Node *myLeft;
        Node *myRight;
        if (l == -1)
            myLeft = NULL;
        else
            myLeft = new Node(l);
        if (r == -1)
            myRight = NULL;
        else
            myRight = new Node(r);

        p->left = myLeft;
        p->right = myRight;

        // 3. children gulo ke push koro
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
    }
    return root;
}
void level_order(Node *root)
{
    if (root == NULL)
    {
        cout << "Tree nai" << endl;
        return;
    }
    queue<Node *> q;
    q.push(root);
    while (!q.empty())
    {
        // 1. ber kore ana
        Node *f = q.front();
        q.pop();

        // 2. jabotiyo ja kaj ache
        cout << f->val << " ";

        // 3. tar children gulo ke rakha
        if (f->left)
            q.push(f->left);
        if (f->right)
            q.push(f->right);
    }
}
void insert(Node *&root, int x)
{
    if (root == NULL)
    {
        root = new Node(x);
        return;
    }
    if (x < root->val)
    {
        if (root->left == NULL)
        {
            root->left = new Node(x);
        }
        else
        {
            insert(root->left, x);
        }
    }
    else
    {
        if (root->right == NULL)
        {
            root->right = new Node(x);
        }
        else
        {
            insert(root->right, x);
        }
    }
}
int main()
{
    Node *root = input_tree();

    insert(root, 13);
    insert(root, 32);
    insert(root, 27);
    insert(root, 22);
    level_order(root);
    return 0;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://phitron.gitbook.io/data-structure/binary-search-tree-implementation/insert-in-bst.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.