वैलिडेट बीएसटी: बाइनरी ट्री पर मिन/मैक्स रेंज (जावा)

टीएल;डीआर

• समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।
• दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.५: जाँचो कि बाइनरी ट्री बाइनरी सर्च ट्री है या नहीं। मुख्य तरीका रिकर्सिव मिन/मैक्स सीमाएँ; इन-ऑर्डर सॉर्टेड स्कैन वैकल्पिक जाँच है।
• जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

बाइनरी सर्च ट्री सिर्फ "बायाँ बच्चा छोटा, दायाँ बच्चा बड़ा" नहीं होता। वह तो सिर्फ सीधे बच्चों को देखता है। असली बीएसटी कहता है: बाएँ सबट्री का हर मान नोड से छोटा, और दाएँ सबट्री का हर मान नोड से बड़ा। कोई दूर का पोता-पोती टूटे तो ट्री बीएसटी नहीं, भले हर स्थानीय पैरेंट-चाइल्ड जोड़ी ठीक लगे।

यह पोस्ट जावा में शुरुआती लोगों के लिए मूल शिक्षण है। इंटरव्यू वाली "बीएसटी वैध है?" परिवार की समस्या, किताब की नकल नहीं। सीटीसीआई जावा सीरीज़ का हिस्सा। अध्याय ४, ट्री और ग्राफ।

---

१. रोज़मर्रा की उपमा

कंपनी का संगठन चार्ट सोचो जहाँ हर मैनेजर की पूरी शाखा पर सैलरी का नियम हो:

• बाएँ डिप्टी के नीचे सबको मैनेजर से कम कमाना चाहिए।
• दाएँ डिप्टी के नीचे सबको मैनेजर से ज्यादा कमाना चाहिए।
• नियम परत-दर-परत लगता है। तीन स्तर नीचे वाला भी ऊपर के हर बॉस की पट्टी में बैठता है।

ट्री में उतरते समय तुम एक वैध सैलरी रेंज ले जाते हो: "min से बड़ा, max से छोटा।" जड़ पर रेंज खुली। बाएँ बच्चे पर पैरेंट का मान नया मैक्स बनता है। दाएँ बच्चे पर पैरेंट का मान नया मिन बनता है। कोई अपनी पट्टी से बाहर गिरे तो चार्ट बीएसटी के रूप में अवैध।

यही पूरा मुख्य एल्गोरिदम है: सिकुड़ती मिन/मैक्स सीमाओं के साथ रिकर्शन।

---

२. समस्या सादे शब्दों में

इनपुट: पूर्णांकों के बाइनरी ट्री की जड़ (TreeNode में left, right, और int मान)।

आउटपुट: ट्री बाइनरी सर्च ट्री हो तो true, नहीं तो false।

यहाँ बीएसटी की परिभाषा:

• हर नोड n के लिए, n.left सबट्री के सभी नोड्स का मान n.data से सख्ती से छोटा।
• n.right सबट्री के सभी नोड्स का मान n.data से सख्ती से बड़ा।
• दोनों सबट्री खुद भी बीएसटी हों।
• खाली ट्री और एक-नोड ट्री बीएसटी हैं।

उदाहरण:

ट्री (जड़ पहले, अनौपचारिक)	वैध बीएसटी?	क्यों
20 बाएँ 10, दाएँ 30	हाँ	रेंज ठीक
20 बाएँ 10, और 10 का दायाँ 25	नहीं	25 बाएँ में है 20 के, पर 25 > 20
20 बाएँ 10, दाएँ 30, और 30 का बायाँ 25	हाँ	25 बीच में 20 और 30
खाली	हाँ	कोई उल्लंघन नहीं
सिर्फ 7	हाँ	एक मान, कोई तुलना नहीं

कोड से पहले स्पष्ट करो:

• बराबर मान चलेंगे? (यह पोस्ट सख्त < और > रखता है। इंटरव्यूअर डुप्लिकेट माने तो एक तरफ़ चुनो, अक्सर बाएँ <= या दाएँ >=, और वही निभाओ।)
• मान Integer.MIN_VALUE / MAX_VALUE तक जा सकते हैं? (Integer की नल सीमाएँ, या long मिन/मैक्स, ताकि असली नोड मान से टकराव न हो।)
• ट्री सीमित और बिना चक्र? (इस समस्या में हाँ।)

---

३. पहले सोचो

गलत: सिर्फ बच्चे जाँचना

// BAD: गहरी उल्लंघनों को चूकता है
boolean naive(TreeNode n) {
    if (n == null) return true;
    if (n.left != null && n.left.data >= n.data) return false;
    if (n.right != null && n.right.data <= n.data) return false;
    return naive(n.left) && naive(n.right);
}

क्लासिक उल्टे उदाहरण पर (20 → बायाँ 10 → दायाँ 25) हर पैरेंट-चाइल्ड जोड़ी क्रम में लगती है, पर 25 20 के बाएँ सबट्री में बैठा है। सादा चेक true लौटाता है। इंटरव्यूअर इस जाल से प्यार करते हैं।

अधूरा-सा: हर नोड पर बाएँ का मैक्स बनाम दाएँ का मिन

बाएँ सबट्री का मैक्स और दाएँ का मिन निकालकर नोड से मिला सकते हो। सावधानी से हर नोड पर चले तो सही, पर बिना मेमो हर नोड पर ओ(एन) काम अक्सर ओ(एन²) बन जाता है। नीचे वाली रेंज एक ही घूमकर ओ(एन) रहती है।

मुख्य: रिकर्सिव मिन/मैक्स रेंज

हर रिकर्सिव कॉल में दो सीमाएँ भेजो:

१. मौजूदा नोड पर min < node.data < max (सीमा नल / "कोई सीमा नहीं" हो तो खुला सिरा)। २. बाएँ पर वही min, नया मैक्स node.data। ३. दाएँ पर नया मिन node.data, वही max। ४. नल नोड: सही।

एक गहराई-पहले घूमना। हर नोड एक बार, पूर्वजों की सबसे सख्त रेंज के ख़िलाफ़।

वैकल्पिक: इन-ऑर्डर क्रमबद्ध होना चाहिए

बीएसटी का इन-ऑर्डर भ्रमण मानों को गैर-घटते (यहाँ: सख्ती से बढ़ते) क्रम में देखता है। इसलिए:

१. इन-ऑर्डर चलो। २. पिछला मान रखो। ३. मौजूदा पिछले से बड़ा न हो तो फेल।

वही ओ(एन) समय। दूसरी जवाब या क्रॉस-चेक के लिए अच्छा। रेंज विधि "यह नोड अवैध क्यों" समझाने में आसान, क्योंकि ठीक वही मिन/मैक्स दिखा सकते हो जो फेल हुआ।

---

४. जावा समाधान

पहले मुख्य समाधान (मिन/मैक्स)। फिर छोटी इन-ऑर्डर वर्शन।

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data) {
        this.data = data;
    }
}

class ValidateBST {

    /** सार्वजनिक एंट्री: खाली ट्री वैध बीएसटी। */
    boolean isBST(TreeNode root) {
        return check(root, null, null);
    }

    /**
     * @param min विशेष निचली सीमा, या नल अगर कोई नहीं
     * @param max विशेष ऊपरी सीमा, या नल अगर कोई नहीं
     */
    private boolean check(TreeNode node, Integer min, Integer max) {
        if (node == null) {
            return true;
        }

        if (min != null && node.data <= min) {
            return false;
        }
        if (max != null && node.data >= max) {
            return false;
        }

        // Left: मान < node.data रहें
        // Right: मान > node.data रहें
        return check(node.left, min, node.data)
                && check(node.right, node.data, max);
    }
}

खराब ट्री पर वॉकथ्रू:

      20
     /
   10
     \
      25

कॉल	नोड	मिन	मैक्स	परिणाम
१	२०	नल	नल	ठीक, बाएँ-दाएँ जाओ
२	१०	नल	२०	ठीक (10 < 20)
३	२५	१०	२०	फेल: 25 >= 20
२० का दायाँ	नल	२०	नल	सही (फेल के बाद शॉर्ट-सर्किट में नहीं पहुँचता)

25 अपने पैरेंट 10 से बड़ा है, इसलिए सिर्फ-बच्चे वाला चेक खुश। रेंज अभी भी दादा के मैक्स 20 को ढोती है, और वही पकड़ती है।

वैकल्पिक इन-ऑर्डर जाँच:

class ValidateBSTInOrder {
    private Integer prev = null;

    boolean isBST(TreeNode root) {
        prev = null;
        return inOrder(root);
    }

    private boolean inOrder(TreeNode node) {
        if (node == null) {
            return true;
        }
        if (!inOrder(node.left)) {
            return false;
        }
        if (prev != null && node.data <= prev) {
            return false;
        }
        prev = node.data;
        return inOrder(node.right);
    }
}

ऑब्जेक्ट दोबारा इस्तेमाल हो तो हर सार्वजनिक कॉल की शुरुआत में prev रीसेट करो। शुद्ध रिकर्सिव वर्शन prev को एक-एलिमेंट ऐरे या छोटा होल्डर बनाकर पास कर सकती है, ताकि "आख़िरी देखा" मान फ़ील्ड के बिना स्टैक पर अपडेट हो।

Integer नल के बजाय long सीमाएँ भी आम हैं:

boolean isBST(TreeNode root) {
    return checkLong(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean checkLong(TreeNode node, long min, long max) {
    if (node == null) return true;
    if (node.data <= min || node.data >= max) return false;
    return checkLong(node.left, min, node.data)
            && checkLong(node.right, node.data, max);
}

यह null चेक बचाता है। हर int नोड मान पर चलता है, क्योंकि int long सेंटीनेल से उसी तरह नहीं टकराता जैसे int सीमाओं पर असली Integer.MIN_VALUE नोड टकराता।

---

५. जटिलता तालिका

तरीका	समय	अतिरिक्त जगह
मिन/मैक्स रिकर्शन	ओ(एन)	स्टैक ओ(एच), एच = ऊँचाई (सबसे खराब तिरछे पर ओ(एन))
इन-ऑर्डर + prev	ओ(एन)	स्टैक ओ(एच)
सिर्फ बच्चे (सादा)	ओ(एन)	ओ(एच), पर गहरी उल्लंघन पर गलत
हर नोड पर बाएँ-मैक्स / दाएँ-मिन (बिना मेमो)	सबसे खराब ओ(एन²)	ओ(एच)

एन नोड्स की संख्या। संतुलित ट्री में स्टैक गहराई लगभग लॉग एन। इंटरव्यू में आमतौर पर ओ(एन) समय और सही वैश्विक नियम चाहिए, सिर्फ स्थानीय पैरेंट-चाइल्ड स्कैन नहीं।

---

६. किनारे के मामले और आम गलतियाँ

इंटरव्यूअर इन्हें छेड़ते हैं:

• खाली ट्री → सही।
• एक नोड → सही।
• डुप्लिकेट → सख्त नियमों में दो बराबर मान फेल। कंपनी की बीएसटी परिभाषा पूछो।
• तिरछा ट्री (लिंक-लिस्ट जैसा) → समय अभी ओ(एन); स्टैक गहराई इंटरव्यू में कम मायने रखती है।
• मान सीमा के बराबर → सख्त बीएसटी में node.data <= min या >= max फेल होना चाहिए।
• पूर्णांक के सिरे → Integer नल सीमाएँ या long सेंटीनेल चुनो ताकि असली Integer.MIN_VALUE चले।

आम गलतियाँ:

१. सिर्फ बच्चों से तुलना। 20 / 10 / 25 ट्री पर क्लासिक गलत-सही। २. बाएँ/दाएँ पर दोनों सीमाएँ उलटी। बाएँ पुराना मिन रखता है, मैक्स = पैरेंट। दाएँ मिन = पैरेंट, पुराना मैक्स। अदल-बदल करो तो वैध ट्री भी फेल। ३. int min = Integer.MIN_VALUE के साथ node.data <= min। वैध जड़ Integer.MIN_VALUE अवैध लगती है। नल सीमा या long लो। ४. इन-ऑर्डर ऑब्जेक्ट में prev रीसेट भूलना। दूसरी कॉल पुराना पिछला मान ले आती है। ५. दोनों तरफ़ बराबरी मानना। डुप्लिकेट नीति एक बार चुनो। बिना सोचे बाएँ <= और दाएँ <= न मिलाओ (प्लेसमेंट की एकता टूटती है)। ६. एक सबट्री ठीक होते ही true। दोनों तरफ़ पास हों: && इस्तेमाल करो, सिर्फ बाएँ का जल्दी true नहीं।

छोटा उपयोग स्केच:

TreeNode root = new TreeNode(20);
root.left = new TreeNode(10);
root.right = new TreeNode(30);
root.left.right = new TreeNode(25); // 20 के नीचे अवैध

ValidateBST v = new ValidateBST();
boolean ok = v.isBST(root); // false

---

७. दोस्त को समझाने वाला सार

वैलिडेट बीएसटी एक सवाल पूछता है: क्या हर नोड उन सीमाओं के अंदर है जो पूर्वज थोपते हैं?

१. परिभाषा: पूरा बायाँ सबट्री < नोड, पूरा दायाँ > नोड, रिकर्सिव। २. सिर्फ बच्चे काफ़ी नहीं। गहरे मान पैरेंट को तोड़े बिना पूर्वज तोड़ सकते हैं। ३. मुख्य समाधान: मिन और मैक्स के साथ रिकर्शन। बाईं कॉल को max = node.data। दाईं कॉल को min = node.data। ४. नल वैध। पहली उल्लंघन पर false। ५. वैकल्पिक: इन-ऑर्डर को सख्ती से बढ़ते मान दिखने चाहिए। वही जटिलता, अलग कहानी। ६. सीमा का प्रकार चुनते समय डुप्लिकेट और पूर्णांक के सिरों का ध्यान।

अगर 20 / 10 / 25 का उल्टा उदाहरण खींच सको, बाएँ रास्ते पर रेंज सिकोड़ सको, और दिखा सको कहाँ मैक्स 20 ने 25 को खारिज किया, तो समस्या ४.५ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: चेक बैलेंस्ड
• अगला: सक्सेसर