बाइनरी सर्च ट्री लेटकोड सॉल्यूशन में खोजें  


कठिनाई स्तर आसान
में अक्सर पूछा सेब आईबीएम
एल्गोरिदम बाइनरी सर्च ट्री कोडिंग साक्षात्कार साक्षात्कार की तैयारी लेटकोड लेटकोड सॉल्यूशंस

इस समस्या में, हमें एक दिया जाता है बाइनरी सर्च ट्री और एक पूर्णांक। हमें दिए गए पूर्णांक के समान मान वाले नोड का पता खोजने की आवश्यकता है। चेक के रूप में, हमें उप-ट्री के प्रीऑर्डर ट्रैवर्स को प्रिंट करने की आवश्यकता है जिसमें यह नोड रूट के रूप में है। यदि पेड़ में दिए गए पूर्णांक के समान कोई मूल्य नहीं है, तो हमें वापस लौटने की आवश्यकता है नल, यानी एक खाली पेड़।

उदाहरण  

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

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

BST में मान 3 के साथ एक नोड होता है, इसलिए हम इसके उप-पेड़ को वापस करते हैं और इसके प्रीव्यूअर ट्रैवर्सल को प्रिंट करते हैं।

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

BST में मान 4 के साथ कोई नोड नहीं है, इसलिए हम NULL लौटाते हैं और "EmST BST" प्रिंट करते हैं।

दृष्टिकोण (पुनरावर्ती)  

आइए हम इस बात पर विचार करें कि इस मामले में एक समस्या उपप्रकार पर कैसे निर्भर करती है। मान लीजिए कि हमारा फ़ंक्शन लक्ष्य मान के साथ नोड का पता देता है, यदि मिला। हम पेड़ की जड़ से शुरू करते हैं। अगर यह नोड है शून्य, यह स्पष्ट है कि हम बाइनरी सर्च ट्री के अंत तक पहुँच चुके हैं और इसलिए लक्ष्य मान के साथ कोई नोड नहीं है। इसलिए, हम लौट आए शून्य। इसी तरह, हम नोड मान लक्ष्य मान के बराबर है, हम इस नोड को वापस करते हैं। अन्यथा, हम जानते हैं कि लक्ष्य-मूल्यवान नोड या तो अंदर होगा बाएं सबट्री या सही वर्तमान रूट का उपप्रकार। हम root.value और लक्ष्य मान की तुलना करके दिशा (बाएं या दाएं) तय कर सकते हैं। तो, हम उसी पुनरावर्ती फ़ंक्शन को कहते हैं जड़ as जड़.बाएं or जड़।

बाइनरी सर्च ट्री लेटकोड सॉल्यूशन में खोजें

कलन विधि

  1. एक फंक्शन बनाएं खोजबस्ट () लक्ष्य पता वापस करने के लिए
  2. If जड़ के बराबर है रिक्त OR जड़ लक्ष्य के समान ही मूल्य है:
    • मूल लौटाओ
  3. यदि root.value लक्ष्य मान से अधिक है:
    1. वापसी searchBST (root.left, val)
  4. वापसी searchBST (root.right, val)
  5. लक्ष्य नोड के प्रीऑर्डर ट्रैवर्सल प्रिंट करें
यह भी देखें
बाइनरी ट्री डेटा संरचना

बाइनरी सर्च ट्री लेटकोड सॉल्यूशन में खोज का कार्यान्वयन

C ++ प्रोग्राम

#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

द्विआधारी खोज ट्री लेटकोड समाधान में खोज की जटिलता विश्लेषण

समय जटिलता

O (H), H = logN = औसत मामलों में BST की ऊँचाई और ओ (एन), एन = सबसे खराब मामलों में BST का आकार। हम सबसे खराब स्थिति में एक बार पेड़ को पीछे छोड़ते हैं जो तब होता है जब बीएसटी तिरछा हो जाता है।

अंतरिक्ष की जटिलता

O (H) औसत मामलों में जब हम प्रत्येक नोड को पार करने के लिए पुनरावर्ती कॉल का उपयोग करते हैं। पर) सबसे खराब स्थिति में। एक महत्वपूर्ण नोट यह है कि कुछ संकलक सक्षम करते हैं पूंछ-प्रत्यावर्तन और उन मामलों में, अंतरिक्ष जटिलता बन जाती है ओ (1).

यह भी देखें
एक पर्वत सरणी में पीक सूचकांक

दृष्टिकोण (Iterative)  

उपरोक्त दृष्टिकोण के समान, हम बाईं या दाईं उप-सीमा पर कूद सकते हैं यदि लक्ष्य मान वर्तमान नोड में मौजूद नहीं है, तो हम इसे असाइन करके पुनरावृति कर सकते हैं रूट = रूट। लेफ्ट or रूट = रूट। राइट जड़ बनने तक हर पुनरावृत्ति पर शून्य। यदि हम पाते हैं कि जड़ का मूल्य किसी भी पुनरावृत्ति पर लक्षित मूल्य के बराबर है, तो हम उस मूल को वापस करते हैं। नहीं तो हम लौटते हैं शून्य।

कलन विधि

  1. एक समान फ़ंक्शन बनाएं खोजबस्ट () वह लक्ष्य नोड का पता देता है
  2. जबकि जड़ is नहीं शून्य:
    • if जड़.वायु लक्ष्य मान के बराबर है
      • वापसी जड़
    • if root.val is अधिक से अधिक लक्ष्य मूल्य से
      • निम्न सबट्री पर जाएं: रूट = रूट। राइट
    • अन्य
      • बाएं सबट्री पर जाएं: रूट = रूट। लेफ्ट
  3. वापसी रिक्त
  4. लक्ष्य नोड के प्रीऑर्डर ट्रैवर्सल प्रिंट करें

बाइनरी सर्च ट्री लेटकोड सॉल्यूशन में खोज का कार्यान्वयन

C ++ प्रोग्राम

#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

द्विआधारी खोज ट्री लेटकोड समाधान में खोज की जटिलता विश्लेषण

समय जटिलता

O (H = logN) औसत मामलों में और पर) सबसे खराब स्थिति में (तिरछे BST), उपरोक्त दृष्टिकोण के समान।

यह भी देखें
सर्पिल रूप में स्तर के आदेश Traversal

अंतरिक्ष की जटिलता

ओ (1) जैसा कि हम केवल निरंतर मेमोरी स्पेस का उपयोग करते हैं।