बाइनरी रूख BST हो वा छैन भनेर जाँच्नको लागि एक कार्यक्रम


कठिनाई तह सजिलो
बारम्बार सोधिन्छ समग्र एडोब अमेजन बुमेरांग वाणिज्य तथ्य ग्रेऑरेंज MakeMyTrip माइक्रोसफ्ट बजेट OYO कोठा Qualcomm स्नैपडल VMware वालमार्ट ल्याबहरू वूकर
बाइनरी खोज रूख बाइनरी रूख ट्री

समस्या वक्तव्य

"बाइनरी रूख BST छ वा छैन भनेर जाँच्नको लागि एक कार्यक्रमले भन्छ" तपाईंलाई बाइनरी रूख दिइन्छ र बाइनरी रूखले बाइनरी खोज रूखको सम्पत्ति सन्तुष्ट पार्छ कि भनेर जाँच्नु पर्छ। त्यसो भए, बाइनरी रूखसँग निम्न गुणहरू छन्: 

  1. बाँया subtree मा नोड हुनु पर्छ मूल भन्दा कम मूल्य
  2. दाँया subtree मा मूल भन्दा डाटा सहित नोडहरू हुनु पर्छ
  3. बायाँ र दायाँ सबट्री आफैंमा बाइनरी खोज रूख हुनुपर्दछ यसको मतलब तिनीहरू आफैले बाइनरी खोज रूखको सम्पत्ती अनुसरण गर्नुपर्दछ।

उदाहरणका

आगत

बाइनरी रूख BST हो वा छैन भनेर जाँच्नको लागि एक कार्यक्रम

YES

स्पष्टीकरण: दिईएको रूखले बाइनरी खोज रुखको सबै गुणहरू अनुसरण गर्दछ। बाँया सबट्रीमा सबै नोडहरू रूटको मान भन्दा सानो हुन्छन्। र उही सहड सबट्रीको लागि जान्छ, नोड्सको रुट भन्दा ठूलो मान हुन्छ। र बायाँ subtree र दायाँ subtree आफैं BST को सम्पत्ती अनुसरण गर्दछ।

आगत

NO

स्पष्टीकरण: रूखले सम्पत्तीको अनुसरण गर्दैन BST, जहाँ बाँया सबट्रीमा सबै नोडहरू मूल भन्दा सानो मान हुनुपर्दछ।

बाइनरी रूख BST हो वा छैन भनेर जाँच्नको लागि एक कार्यक्रमको लागि दृष्टिकोण

भोली दृष्टिकोण (गलत दृष्टिकोण)

यहाँ हामी केवल एउटा प्रोग्राम लेख्छौं जसले जाँच गर्दछ कि बायाँ उपट्रीको जड़ मूल मान भन्दा सानो छ भने। र सहि subtree को जरा रूट भन्दा ठूलो मूल्य छ। फेरी पुनरावृत्ति बायाँ र दायाँका उपशीर्षकहरूको लागि जाँच गर्नुहोस्। तर यो दृष्टिकोण गलत छ किनकि बायाँ subtree मूल जरा भन्दा सानो छ। बाँया सबट्रीमा त्यहाँ केही नोड हुन सक्दछ जुन रूटको तुलनामा अधिक मूल्यमा हुन्छ। त्यस्तै सही subtree को लागी। त्यसो भए त्यस अवस्थामा यो दृष्टिकोण असफल हुन्छ।

दिईएको रूख (छवि) मा एल्गोरिथ्म चलाउनुहोस्। तपाईंले पाउनुहुनेछ यद्यपि एल्गोरिथ्मले फर्कने छ कि दिईएको बाइनरी ट्री BST हो। तर किनकि १ दायाँ सबट्रीमा २ भन्दा सानो छ। त्यसैले हामीले केही अन्य दृष्टिकोणहरू खोज्नु पर्छ।

दक्ष दृष्टिकोण (सही दृष्टिकोण)

हामी हाम्रो बायाँ र दाँया उपशीर्षकहरूको दायरा परिभाषित गर्न दुई भ्यारीएबल न्यूनतम र अधिकतम प्रयोग गर्नेछौं। यसले हामीलाई बताउँदछ कि यदि बाँया उपशीटमा एलिमेन्टहरू केही दायरामा छन् भने। यो दायरा परिवर्तन भइरहनेछ किनकी हामी उपशीर्षकहरू परिवर्तन गर्दैछौं। यो विधि भर्खर हामी एक भोली दृष्टिकोण मा सामना को त्रुटि हटाउन को लागी प्रयोग गरीन्छ। त्यहाँ हामी ग्यारेन्टी गर्न सक्षम भएनौं कि बाँया सबट्रीमा सबै तत्वहरू जरा भन्दा सानो हुनेछन्। र दाँया सबट्रीमा सबै तत्वहरू जरा भन्दा ठूलो हुनेछ। प्रारम्भमा, हामी हाम्रो BST परीक्षकलाई न्यूनतम सेटको साथ न्यूनतम मानको रूपमा मान र अधिकतम पूर्णांकको अधिकतम मानको रूपमा कल गर्नेछौं। किनभने त्यो दायरा हो जुन मूलको मानलाई पूरा गर्नुपर्दछ। अब हामी रूटको मान -१ को रूपमा बायाँ सबट्रीको अधिकतम अद्यावधिक गर्नेछौं र दायाँ उपशीटिकाका लागि, हामीले न्यूनतम मानलाई मूलको मानको रूपमा सेट गर्नेछौं। अब हामी न्यूनतम र अधिकतम उचित मान सेट गर्न जारी राख्नेछौं र दोहोर्याएर कार्यलाई बायाँ र दाँया subtree को लागि कल गर्दछौं।

कोड

C ++ कार्यक्रम यदि बाइनरी रूख BST हो वा होइन भनेर जाँच गर्न

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

struct node{
    int data;
    node *left;
    node *right;
} ;

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}

bool isThisBST(node* root, int minimum, int maximum)
{
    // if there is no tree
    if(!root)
        return true;

    // the root should be in the range defined by [minimum, maximum]
    if(root->data < minimum || root->data > maximum)
        return false;
    // if the root satisfies the value then we recursively check the same for left and right subtree
    // we set the minimum and maximum for left and right subtrees accordingly.
    return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}

int main()
{
    node *root = create(2);
    root->left = create(1);
    root->right = create(4);
    root->right->left = create(3);
    root->right->right = create(5);

    bool isBST = isThisBST(root, INT_MIN, INT_MAX);
    cout<<((isBST == true) ? "YES" : "NO");
    return 0;
}
YES

जाभा प्रोग्राम जाँच गर्नका लागि यदि बाइनरी रूख BST हो वा होईन

// Class that denote a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
} 

class Tree 
{ 
    static Node root; 
  
  // return true if the tree is BST else return false
    static boolean isThisBST(Node root, int minimum, int maximum)
    { 
        // if there is no tree
      if(root == null)
          return true;
  
      // the root should be in the range defined by [minimum, maximum]
      if(root.data < minimum || root.data > maximum)
          return false;
      // if the root satisfies the value then we recursively check the same for left and right subtree
      // we set the minimum and maximum for left and right subtrees accordingly.
      return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new Node(2); 
        tree.root.left = new Node(1); 
        tree.root.right = new Node(4); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(5); 
  
        boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    	System.out.print((isBST == true) ? "YES" : "NO");
    }
}
YES

जटिलता विश्लेषण

समय जटिलता

O (N), किनकि हामी केवल रूखको माध्यमबाट हिडेका छौं। र एकल traversal लागत रेखा समय जटिलता।

ठाउँ जटिलता

O (१) स्थिर ठाउँ किनकि हामी केवल भेरियबलको स्थिर संख्या प्रयोग गर्थ्यौं तर सम्पूर्ण कार्यक्रमले ओ (एन) लिन्छ किनकि रूखमा एन नोडहरू छन्।