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

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

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

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

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

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

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)

Full code:

#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;
}