बायनरी सर्च ट्री लेटकोड सोल्यूशनमध्ये शोधा


अडचण पातळी सोपे
वारंवार विचारले सफरचंद IBM
बायनरी शोध वृक्ष

या समस्येमध्ये, आम्हाला ए बायनरी शोध वृक्ष आणि पूर्णांक आम्हाला दिलेल्या पूर्णांकासारखे मूल्य असलेल्या नोडचा पत्ता शोधणे आवश्यक आहे. तपासणी म्हणून, आम्हाला उप-वृक्षाचे प्रीऑर्डर ट्रव्हर्सल मुद्रित करणे आवश्यक आहे ज्यामध्ये हा नोड मूळ आहे. जर झाडामध्ये दिलेल्या पूर्णांकासारखे कोणतेही मूल्य नसेल तर आपण परत जाणे आवश्यक आहे निरर्थकम्हणजेच रिक्त झाड.

उदाहरण

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

स्पष्टीकरण # 1

बीएसटी मध्ये मूल्य 3 सह नोड आहे, म्हणून आम्ही त्याचे उप-वृक्ष परत मिळवितो आणि प्रीऑर्डर ट्रॅव्हर्सल मुद्रित करतो.

स्पष्टीकरण # 2

बीएसटी मध्ये मूल्य 4 सह कोणतेही नोड नसते, म्हणून आम्ही शून्य परत करतो आणि “रिक्त बीएसटी” मुद्रित करतो.

दृष्टीकोन (रिकर्सीव्ह)

या प्रकरणात एखादी समस्या सबप्रोब्लमवर कशी अवलंबून असते याचा विचार करूया. समजा आमचे कार्य आढळल्यास लक्ष्य मूल्य असलेल्या नोडचा पत्ता परत करते. आम्ही झाडाच्या मुळापासून सुरूवात करतो. जर हे नोड असेल निरर्थक, हे स्पष्ट आहे की आम्ही बायनरी शोध वृक्षाच्या शेवटी पोहोचलो आहोत आणि म्हणून लक्ष्य मूल्यासह कोणतेही नोड नाही. तर, आम्ही परत निरर्थक. त्याचप्रमाणे आपल्याकडे नोडचे मूल्य लक्ष्य मूल्याइतके असते, आम्ही हे नोड परत करतो. अन्यथा, आम्हाला माहित आहे की लक्ष्य-मूल्यवान नोड एकतर असेल बाकी सबट्री किंवा योग्य वर्तमान रूटची उपशीर्षक. आम्ही root.value आणि लक्ष्य मूल्याची तुलना करून दिशा (डावी किंवा उजवी) ठरवू शकतो. म्हणून आम्ही त्याच रिकर्सिव्ह फंक्शनला कॉल करतो मूळ as root.left or root.right.

बायनरी सर्च ट्री लेटकोड सोल्यूशनमध्ये शोधा

अल्गोरिदम

  1. एक फंक्शन तयार करा शोध बीएसटी () लक्ष्य पत्ता परत करण्यासाठी
  2. If मूळ च्या बरोबर आहे निरर्थक OR मूळ लक्ष्याइतकेच मूल्य आहे:
    • रिटर्न रूट
  3. जर रूट.व्हॅल्यू लक्ष्य मूल्यापेक्षा जास्त असेल तर:
    1. परत सर्च बीएसटी (रूट. लेफ्ट, व्हॅल)
  4. परत सर्च बीएसटी (रूट. राइट, व्हॅल)
  5. लक्ष्य नोडची प्रीऑर्डर ट्रव्हर्सल मुद्रित करा

बायनरी सर्च ट्री लेटकोड सोल्यूशनमध्ये शोधाची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

जावा कार्यक्रम

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

बायनरी सर्च ट्री लीटकोड सोल्यूशनमध्ये शोधाची जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एच), एच = लॉगएन = सरासरी प्रकरणांमध्ये बीएसटीची उंची आणि ओ (एन), एन = सर्वात वाईट परिस्थितीत बीएसटीचा आकार. आम्ही सर्वात वाईट परिस्थितीत एकदा झाडाला वळण लावतो जे जेव्हा बीएसटी स्कूइंग होते तेव्हा होते.

जागेची जटिलता

ओ (एच) सरासरी प्रकरणांमध्ये आम्ही प्रत्येक नोडला जाण्यासाठी रिकर्सिव्ह कॉल वापरतो. ओ (एन) सर्वात वाईट परिस्थितीत. एक महत्वाची नोंद अशी आहे की काही कंपाइलर सक्षम करतात शेपटी-पुनरावृत्ती आणि त्या प्रकरणांमध्ये, जागेची जटिलता बनते ओ (1).

दृष्टीकोन (Iterative)

वरील पध्दती प्रमाणेच, जर लक्ष्य मूल्य सध्याच्या नोडमध्ये नसल्यास डावी किंवा उजवी उपशाखावर जाऊ शकतो, तर हे नियुक्त करून पुनरावृत्ती करू शकतो. रूट = रूट.लेफ्ट or रूट = रूट.राईट प्रत्येक पुनरावृत्तीवर रूट होईपर्यंत निरर्थक. कोणत्याही पुनरावृत्तीच्या वेळी रूटचे मूल्य लक्ष्य मूल्याच्या बरोबरीचे असल्यास आपल्याला ते मूळ परत मिळते. अन्यथा, आम्ही परत निरर्थक.

अल्गोरिदम

  1. एक समान कार्य तयार करा शोध बीएसटी () ते लक्ष्य नोडचा पत्ता परत करते
  2. तर मूळ is नाही निरर्थक:
    • if root.value लक्ष्य मूल्याच्या समान आहे
      • परत मूळ
    • if रूट.वल is मोठे लक्ष्य मूल्यापेक्षा
      • उजवीकडील सबट्रीवर जा: रूट = रूट.राईट
    • आणखी
      • डावीकडील सबट्रीवर जा: रूट = रूट.लेफ्ट
  3. परत निरर्थक
  4. लक्ष्य नोडची प्रीऑर्डर ट्रव्हर्सल मुद्रित करा

बायनरी सर्च ट्री लेटकोड सोल्यूशनमध्ये शोधाची अंमलबजावणी

सी ++ प्रोग्राम

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int val)
    {
        value = val;
        left = right = NULL;
    }
};

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

जावा कार्यक्रम

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

बायनरी सर्च ट्री लीटकोड सोल्यूशनमध्ये शोधाची जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एच = लॉगएन) सरासरी प्रकरणांमध्ये आणि ओ (एन) सर्वात वाईट परिस्थितीत (बीएसटी स्क्यूड), वरील पद्धतीप्रमाणेच.

जागेची जटिलता

ओ (1) आपण केवळ मेमरी स्पेस वापरत आहोत.