মডিউল ২১-৩ঃ Search in BST

Binary SearchTree এ duplicate value নিয়ে আমরা গত module এ জেনেছি। এই module এ আমরা binary search tree এর search operation দেখবো।

এই module এ আমরা আগে code থেকে বুঝবো তারপর complexity বুঝবো।

প্রথমে এভাবে Node নিয়ে নিবো doubly linked list এর মতো।

class Node
{
public:
    int val;
    Node *left;
    Node *right;
    Node(int val)
    {
        this->val = val;
        this->left = NULL;
        this->right = NULL;
    }
};

এরপর input function বানাতে হবে যাতে করে আমরা bst তে value input নিতে পারি।

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. এখানে queue এর front বের করে আনা হবে।
        Node *p = q.front();
        q.pop();

        // 2. এখানে left & right child গুলো নেয়া হবে।
        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 গুলো push করতে হবে
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
    }
    return root;
}

এরপর একটা search function বানাতে হবে। এই function একটা root নিতে হবে আরেকটা value. এর পর বাকিটা code এ দেখা যাক।

bool search(Node *root, int x)
{
//base condition এ null পাওয়া মানে value পাওয়া যায়নি. তাই false return করতে হবে।
    if (root == NULL) 
        return false;
//base condition এ value x পাওয়া গিয়েছ তাই true return করতে হবে।
    if (root->val == x)
        return true;

//এরপর root এর value x থেকে বড় হলে left এ যেতে হবে আর ছোট হলে right এ 
    if (x < root->val)
        return search(root->left, x);
    else
        return search(root->right, x);
}


এর পর আসবে main function 

int main()
{
// এখানে root node এ input function call করবো যা আমাদের একটা tree এর node  return করবে।
    Node *root = input_tree();
// এখন search function কে call করে tree তে 100 পাওয়া যায় কিনা দেখা হচ্ছে।
    if (search(root, 100))
        cout << "Yes, Found" << endl;
    else
        cout << "No, Not Found" << endl;
    return 0;
}

BST এর Time complexity: O (h) or O (height)

Best Case: O(logN)

(Perfect or complete binary tree এর ক্ষেত্রে)

Worst Case: O(N)

(কোনো level complete না থাকলে সে ক্ষেত্রে)

এখানে height এর উপর যেহেতু BST er time complexity depend করে তাই এর time complexity আমরা বলতে পারি

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);
    }
}
bool search(Node *root, int x)
{
    if (root == NULL)
        return false;
    if (root->val == x)
        return true;
    if (x < root->val)
        return search(root->left, x);
    else
        return search(root->right, x);
}
int main()
{
    Node *root = input_tree();
    if (search(root, 100))
        cout << "Yes, Found" << endl;
    else
        cout << "No, Not Found" << endl;
    return 0;
}