सक्सेसर: द्विआधारी खोज वृक्ष में इन-ऑर्डर अगला नोड (जावा)

टीएल;डीआर

समस्या: डेटा संरचनाओं और एल्गोरिदम के लिए समय और स्थान जटिलता (टाइम एंड स्पेस कॉम्प्लेक्सिटी) का अनुकूलन।

दृष्टिकोण: शुरुआती लोगों के लिए सीटीसीआई शैली की समस्या ४.६: हर नोड पर पैरेंट लिंक हो तो द्विआधारी खोज वृक्ष में किसी नोड का इन-ऑर्डर सक्सेसर ढूँढो। दाएँ उपवृक्ष का सबसे बायाँ, या जब तक दायाँ संतान हो तब तक पैरेंट चढ़ो।

जटिलता: सीमांत मामलों (एज केसेस) के प्रबंधन के साथ इष्टतम समय और मेमोरी संतुलन।

द्विआधारी खोज वृक्ष का इन-ऑर्डर घुमाव कुंजियाँ क्रम में छापता है। किसी एक नोड का सक्सेसर वही अगली कुंजी है जिसे वह घुमाव अगले कदम पर छूता। जड़ से फिर पूरा वृक्ष नहीं घूमते। नोड पहले से हाथ में है, और हर नोड के पास parent सूचक है।

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

१. क्रम वाली पंक्ति की उपमा

द्विआधारी खोज वृक्ष को ऊँचाई (या कुंजी) के हिसाब से खड़ी लोगों की पंक्ति समझो। इन-ऑर्डर मतलब: बायाँ उपवृक्ष, फिर मैं, फिर दायाँ उपवृक्ष। किसी का सक्सेसर उस पंक्ति में ठीक दाहिनी ओर खड़ा व्यक्ति है।

पूरी पंक्ति दोबारा खींचे बिना दो रास्ते:

दाहिनी शाखा है। अगला तुम्हारा सीधा दायाँ संतान नहीं। वह शाखा का सबसे बायाँ व्यक्ति है (तुमसे बड़ी पर सबसे छोटी कुंजी)।
दाहिनी शाखा नहीं। बायाँ और खुद खत्म। जड़ की ओर चढ़ो जब तक तुम किसी के दाएँ संतान हो। पहला पूर्वज जहाँ तुम बाएँ बैठे हो, वही पंक्ति का अगला। जड़ पार हो गए तो तुम आखिरी थे।

पैरेंट लिंक सीढ़ी हैं। उनके बिना हर बार जड़ से खोजना पड़ता।

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

लक्ष्य: द्विआधारी खोज वृक्ष के नोड n का इन-ऑर्डर सक्सेसर लौटाओ, या आखिरी होने पर null।

मान्यताएँ:

नोड में left, right, और parent हों।
वृक्ष द्विआधारी खोज वृक्ष है (बाएँ छोटी, दाएँ बड़ी कुंजियाँ), या कम से कम संरचनात्मक इन-ऑर्डर अगला नोड चाहिए।
सिर्फ n से शुरू; अलग से जड़ नहीं, जब तक चढ़कर न पहुँचो।

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

n नल हो तो? (नल लौटाओ।)
n का न पैरेंट न दायाँ संतान? (जड़ और आखिरी; नल लौटाओ।)
दोहरी कुंजी? (अक्सर अद्वितीय मानते हैं। पूछे तो अपना नियम बताओ।)

३. पहले सोचो

गलत पहला ख्याल: पूरा इन-ऑर्डर ढेर

पूरा वृक्ष सूची में डालो, n ढूँढो, अगला सूचकांक लौटाओ। सही, पर समय और जगह दोनों ओ(एन)। इंटरव्यू पैरेंट से ओ(एच) चाहता है, जहाँ एच ऊँचाई है।

स्थिति क: दायाँ संतान मौजूद

सक्सेसर दाएँ उपवृक्ष का न्यूनतम:

१. n.right पर जाओ। २. जब तक left नल न हो, बाएँ चलो। ३. वही नोड उत्तर है।

क्यों? इन-ऑर्डर बायाँ, नोड, दायाँ करता है। n के बाद दाएँ उपवृक्ष में पहली यात्रा उसके सबसे बाएँ नोड पर होती है।

स्थिति ख: दायाँ संतान नहीं

पैरेंट चढ़ो:

१. p = n.parent, c = n रखो। २. जब तक p नल न हो और c == p.right (अभी भी दायाँ संतान), c = p, p = p.parent करो। ३. p लौटाओ (आखिरी नोड हो तो नल हो सकता है)।

क्यों? एक दायाँ उपवृक्ष खत्म हुआ। तब तक चढ़ो जब तक बाएँ से किसी नोड में प्रवेश न हो। वह नोड मानसिक इन-ऑर्डर में अभी "छुआ" नहीं गया।

खाका

        20
       /  \
     10    30
    /  \     \
   5   15    40
      /
    12

नोड	सक्सेसर	क्यों
१०	१२	दायाँ संतान १५; उस शाखा का सबसे बायाँ १२
१५	२०	दायाँ नहीं; १५, १० का दायाँ, चढ़ो; १०, २० का बायाँ → २०
४०	नल	दायाँ नहीं; ३० फिर २० के दाएँ चढ़ो; जड़ का पैरेंट नहीं
५	१०	दायाँ नहीं; ५, १० का बायाँ → पैरेंट १०

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

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

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

class Solution {
    /** In-order successor of n, or null if n is last / null. */
    TreeNode inOrderSuccessor(TreeNode n) {
        if (n == null) {
            return null;
        }

        // Case A: right subtree exists → leftmost of right
        if (n.right != null) {
            return leftMostChild(n.right);
        }

        // Case B: climb until we are not a right child
        TreeNode current = n;
        TreeNode p = n.parent;
        while (p != null && p.right == current) {
            current = p;
            p = p.parent;
        }
        return p;
    }

    private TreeNode leftMostChild(TreeNode n) {
        if (n == null) {
            return null;
        }
        while (n.left != null) {
            n = n.left;
        }
        return n;
    }
}

सहायक नोट:

leftMostChild वही विचार है: "उपवृक्ष में न्यूनतम"।
चढ़ाई लूप तब रुकता है जब p == null (कोई सक्सेसर नहीं) या current हो p.left (अगला पूर्वज मिला)।
पैरेंट पूरे हों तो जड़ अलग तर्क में नहीं चाहिए।

वैकल्पिक: इंटरव्यूअर पैरेंट मना करे तो जड़ से उम्मीदवार के साथ खोज (चलते हुए n से बड़ी आखिरी कुंजी)। अलग सेटअप; यह पोस्ट पैरेंट लिंक पर टिका है।

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

तरीका	समय	अतिरिक्त जगह
पैरेंट-लिंक सक्सेसर (यह हल)	ओ(एच)	ओ(१)
पूरा इन-ऑर्डर सूची फिर सूचकांक	ओ(एन)	ओ(एन)
बिना पैरेंट जड़ से (उम्मीदवार)	ओ(एच)	ओ(१)

एच वृक्ष की ऊँचाई। संतुलित ≈ लॉग एन। तिरछा एन तक। पैरेंट घुमाव की जगह स्थिर।

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

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

नल इनपुट → नल लौटाओ।
सबसे दायाँ नोड → जड़ तक चढ़ो, फिर नल। इन-ऑर्डर आखिरी का सक्सेसर नहीं।
जड़ सिर्फ बाएँ उपवृक्ष के साथ → जड़ का सक्सेसर माँगो और दायाँ न हो तो नल (दायाँ न हो तो जड़ आखिरी)।
बायाँ संतान वाला पत्ता → सक्सेसर उसका पैरेंट (लूप लगभग नहीं घूमेगा)।
गहरी दाईं रीढ़ → कई पैरेंट छू सकते हो; फिर भी ओ(एच), गलती नहीं।

आम गलतियाँ:

१. सीधा दायाँ संतान लौटाना, दाएँ उपवृक्ष का सबसे बायाँ नहीं। बाईं श्रृंखला छूट जाती है। २. हमेशा सिर्फ एक पैरेंट चढ़ना। जब तक दायाँ संतान हो, लूप चलना चाहिए। ३. जड़ पर पैरेंट नल भूलकर p.right पर नल-पॉइंटर एरर। ४. सक्सेसर को प्रीडेसेसर समझना। प्रीडेसेसर सममित: बायाँ न हो तो बाएँ संतान रहते चढ़ो; या बाएँ उपवृक्ष का सबसे दायाँ। ५. समय बताते संतुलित मान लेना। ओ(एच) कहो, सबसे खराब ओ(एन)। ६. वृक्ष बदलकर अस्थायी पैरेंट जोड़ना। पहले से हों तो ज़रूरत नहीं।

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

// Build a tiny tree with parents set both ways, then:
TreeNode fifteen = /* node 15 */;
TreeNode next = new Solution().inOrderSuccessor(fifteen); // 20 in the sketch above

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

सक्सेसर मतलब द्विआधारी खोज वृक्ष के एक नोड के लिए "क्रम / इन-ऑर्डर में अगला कौन":

१. नोड का दायाँ संतान हो तो एक बार दाएँ जाओ, फिर जब तक हो बाएँ। वही अगला। २. नहीं तो जब तक दायाँ संतान हो पैरेंट चढ़ो। बाएँ से मिला पहला पैरेंट अगला। ३. पैरेंट खत्म तो कोई अगला नहीं। ४. पैरेंट सूचक से समय ओ(ऊँचाई), अतिरिक्त जगह ओ(१)। पूरा वृक्ष नहीं डालना।

सफेद बोर्ड पर दोनों स्थितियाँ खींच सको और नमूना वृक्ष पर १५ → २० तथा ४० → नल चला सको, तो समस्या ४.६ तुम्हारी है।