चेक बैलेंस्ड: ऊँचाई का अंतर अधिकतम एक (जावा)

टीएल;डीआर

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

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

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

---

१. संतुलन जैसे स्पिरिट लेवल

छत से लटके मोबाइल की हर जोड़ पर स्पिरिट लेवल रखो। हर जोड़ का बायाँ बाजू और दायाँ बाजू है। बाजू थोड़े अलग हो सकते हैं (एक "निशान"), पर दो या ज़्यादा नहीं। कोई जोड़ तिरछा हो तो सिर्फ ऊपर का हुक नहीं, पूरा मोबाइल फेल।

द्विआधारी वृक्ष में:

• पत्ती की ऊँचाई ० (या १, तुम्हारे नियम पर; एक चुनकर उसी पर टिके रहो)।
• नोड की ऊँचाई 1 + max(height(left), height(right))।
• उस नोड पर |height(left) - height(right)| अधिकतम १ होना चाहिए।
• अगर पत्तियाँ ऊँचाई ० रखती हैं तो शून्य बच्चे की ऊँचाई -१। शून्य को -१ और पत्ती को ० लगातार मानो।

नीचे इस्तेमाल इंटरव्यू वाला नियम: शून्य की ऊँचाई -१, पत्ती की ऊँचाई 0, दो पत्तियों वाले नोड की ऊँचाई 1।

---

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

लक्ष्य: द्विआधारी वृक्ष संतुलित हो तो true, नहीं तो false।

परिभाषा: हर नोड पर दोनों उपवृक्षों की ऊँचाइयाँ अधिकतम १ से अलग। दोनों उपवृक्ष अंदर से भी संतुलित हों।

इनपुट: द्विआधारी वृक्ष की जड़ (TreeNode में left और right)।

आउटपुट: बूलियन।

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

• खाली वृक्ष (null जड़): संतुलित (true)।
• शून्य की ऊँचाई: -1 (आम) या 0 (ठीक अगर एक जैसा नियम हो)।
• परफेक्ट / कम्प्लीट / फुल वृक्ष: नज़दीकी शब्द, यहाँ "संतुलित" नहीं। ऊँचाई-अंतर की परिभाषा पर रहो।

उदाहरण

वृक्ष का स्केच	संतुलित?	क्यों
अकेला नोड	हाँ	दोनों तरफ़ शून्य
जड़ पर सिर्फ बायाँ बच्चा	हाँ	ऊँचाइयाँ ० और -१, अंतर १
तीन नोड की बाईं श्रृंखला, जड़ के नीचे दाईं शाखा नहीं	नहीं	जड़ पर बाईं ऊँचाई १, दाईं -१, अंतर २
ऊँचाई २ का छोटा भरा वृक्ष	हाँ	हर नोड ० या १ से अलग

---

३. पहले सोचो

सीधा तरीका: हर नोड पर ऊँचाई हेल्पर दो बार

isBalanced(n):
  if n is null: return true
  hl = height(n.left)
  hr = height(n.right)
  if |hl - hr| > 1: return false
  return isBalanced(n.left) and isBalanced(n.right)

सही। धीमा। height हर उपवृक्ष घूमता है, और तुम हर नोड पर बुलाते हो, इसलिए वही नोड बार-बार छूते हो। सबसे खराब संतुलित वृक्ष पर लगभग ओ(एन लॉग एन), टेढ़े पर ओ(एन²)।

पसंदीदा: एक पास, ऊँचाई या असफल संकेत

नीचे से ऊपर ऊँचाई निकालते हुए संतुलन नियम भी जाँचो। उपवृक्ष पहले से असंतुलित हो तो असली ऊँचाई मत लौटाओ। असफल सेंटीनल लौटाओ (छोटे स्केच में अक्सर -1; नीचे Integer.MIN_VALUE ताकि शून्य ऊँचाई -1 से टकराए नहीं)।

इंटरव्यू वाला साफ पैटर्न:

• हेल्पर संतुलित उपवृक्ष की ऊँचाई लौटाता है।
• उपवृक्ष असंतुलित हो तो असफल सेंटीनल।
• माता-पिता किसी भी बच्चे से सेंटीनल देखकर ऊपर भेज देते हैं, और काम नहीं।
• सार्वजनिक विधि: checkHeight(root) != UNBALANCED।

यह एक डीएफएस है, समय ओ(एन), स्टैक ओ(एच)। ऊपर आते हुए पहला खराब नोड मिलते ही जल्दी बाहर।

नीचे-से-ऊपर क्यों: माता-पिता तय करने से पहले दोनों बच्चों की ऊँचाई चाहिए। पोस्ट-ऑर्डर स्वाभाविक है। प्री-ऑर्डर "पहले मुझे जाँचो, फिर रीकर्स" फिर भी दोनों तरफ़ पूरी ऊँचाई माँगता है, तो फिर से घूमना या कैश। ऊँचाई+जाँच मिला एक पास साफ जोड़ है।

---

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

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

class CheckBalanced {
    // Distinct from null height (-1) so failure never looks like an empty child.
    private static final int UNBALANCED = Integer.MIN_VALUE;

    public boolean isBalanced(TreeNode root) {
        return checkHeight(root) != UNBALANCED;
    }

    /** Height if this subtree is balanced; UNBALANCED if any node fails. */
    private int checkHeight(TreeNode node) {
        if (node == null) {
            return -1;
        }

        int left = checkHeight(node.left);
        if (left == UNBALANCED) {
            return UNBALANCED;
        }

        int right = checkHeight(node.right);
        if (right == UNBALANCED) {
            return UNBALANCED;
        }

        if (Math.abs(left - right) > 1) {
            return UNBALANCED;
        }

        return Math.max(left, right) + 1;
    }
}

-1 दोबारा इस्तेमाल क्यों नहीं, Integer.MIN_VALUE क्यों? शून्य की ऊँचाई पहले से -1 है। अगर "असंतुलित" के लिए भी -1 रखो तो माता-पिता "बायाँ बच्चा गायब" और "बायाँ उपवृक्ष फेल" अलग नहीं कर पाते। अलग असफल सेंटीनल कमरे में समझाना आसान है।

चलकर देखो (संतुलित):

      1
     / \
    2   3
   /
  4

• नोड ४: बायाँ -१, दायाँ -१, अंतर ०, ऊँचाई ०।
• नोड २: बायाँ ०, दायाँ -१, अंतर १, ऊँचाई १।
• नोड ३: बायाँ -१, दायाँ -१, अंतर ०, ऊँचाई ०।
• नोड १: बायाँ १, दायाँ ०, अंतर १, ऊँचाई २।
• checkHeight २ लौटाता है, UNBALANCED नहीं → true।

चलकर देखो (असंतुलित):

    1
   /
  2
 /
3

• नोड ३: ऊँचाई ०।
• नोड २: बायाँ ०, दायाँ -१, ऊँचाई १।
• नोड १: बायाँ १, दायाँ -१, अंतर २ → UNBALANCED → false।

---

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

तरीका	समय	अतिरिक्त जगह	नोट
हर नोड पर ऊँचाई हेल्पर	ओ(एन लॉग एन) से ओ(एन²)	ओ(एच) रीकर्शन	सरल, आदर्श नहीं
एक पास ऊँचाई + असफल संकेत	ओ(एन)	ओ(एच) स्टैक	हर नोड एक बार
साफ स्टैक डीएफएस, वही तर्क	ओ(एन)	ओ(एच)	इंटरव्यू में कम; रीकर्शन काफी

एच वृक्ष की ऊँचाई है। टेढ़ा वृक्ष: एच = एन, स्टैक ओ(एन)। संतुलित: एच = लॉग एन।

---

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

इंटरव्यूअर यहाँ चुभोते हैं:

• शून्य जड़ → संतुलित।
• अकेला नोड → संतुलित।
• किसी गहरे नोड के नीचे एक लंबा बाजू, जड़ अभी भी "छोटी" लगे → फिर भी गलत; सिर्फ जड़ नहीं, हर नोड जाँचो।
• अंतर ठीक १ → मान्य। अंतर २ → फेल।
• दोनों उपवृक्ष ऊँचे पर बराबर → ठीक अगर हर तरफ़ अंदर संतुलित हो।

आम गलतियाँ:

१. सिर्फ जड़ पर ऊँचाई तुलना। बच्चे के नीचे गहरा असंतुलन फिर भी असंतुलन है। २. हर नोड पर बाएँ-दाएँ अलग height। जवाब सही, वर्ग जोखिम। मिला पास अपनाओ। ३. शून्य ऊँचाई और फेल दोनों के लिए -1। उलझन। अलग असफल सेंटीनल रखो। ४. जल्दी वापसी भूलना। बच्चा फेल हो तो ऊपर भेजो; जवाब पहले से गलत हो तो भाई की ऊँचाई मापना ज़रूरी नहीं (वैकल्पिक अनुकूलन; खराब नोड आखिरी हो तो सबसे खराब फिर ओ(एन))। ५. शून्य ऊँचाई पर एक का फर्क। शून्य = -१ और पत्ती = ० से max + 1 साफ रहता है। शून्य = ० हो तो पत्ती १ बनती है; ज़ोर से बोलो ताकि इंटरव्यूअर तुम्हारे अंक पकड़े। ६. एवीएल बनाम "संतुलित"। यहाँ "संतुलित" ऊँचाई-अंतर की परिभाषा है, पूरा एवीएल इनसर्ट वॉकथ्रू नहीं जब तक न पूछें।

छोटा इस्तेमाल:

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
boolean ok = new CheckBalanced().isBalanced(root); // true

---

७. दोस्त को समझाओ सार

चेक बैलेंस्ड एक वृक्ष डीएफएस है जो दो काम एक में जोड़ता है:

१. ऊँचाई परिभाषा: शून्य -१, वरना 1 + max(left, right)। २. हर नोड पर दोनों बच्चे जवाब दें तो, कोई फेल हो तो तुम फेल। |left - right| > 1 हो तो फेल। ३. नहीं तो अपनी ऊँचाई लौटाओ ताकि माता-पिता वही जाँच करें। ४. सार्वजनिक एपीआई बूलियन है: हेल्पर असफल सेंटीनल नहीं लौटाया।

अगर तीन नोड की बाईं श्रृंखला खींच सको, जड़ पर अंतर २ दिखा सको, और ओ(एन) एक-पास हेल्पर से तुलना कर सको, तो समस्या ४.४ तुम्हारी है। अगला: बीएसटी रेंज जाँचना, वही पुनरावृत्ति रीढ़, अलग नियम।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: लिस्ट ऑफ़ डेप्थ्स
• अगला: वैलिडेट बीएसटी