बीएसटी सीक्वेंसेस: वही पेड़ बनाने वाले सभी ऐरे (जावा)

टीएल;डीआर

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

खाली बाइनरी सर्च ट्री में संख्याएँ एक-एक करके डालते हो। हमेशा जड़ से चलते हो और पहला खाली बच्चे का स्थान पाते हो। अंतिम आकार क्रम पर निर्भर करता है। अलग-अलग ऐरे एक ही पेड़ बना सकते हैं। समस्या ४.९ उल्टी पूछती है: तैयार बीएसटी दिया हो तो हर वह ऐरे छापो जो इसे बना सकता था।

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

---

१. ताश के पत्तों की उपमा

एक डीलर सोचो जो ऊपर वाले एक पत्ते के नीचे दो तरफ़ के ढेर बनाता है:

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

पूरा जवाब: जड़ पहले, फिर बाएँ अनुक्रम और दाएँ अनुक्रम का हर वैध वीव।

छोटा पेड़:

    2
   / \
  1   3

सिर्फ दो इंसर्शन ऐरे:

• {2, 1, 3}
• {2, 3, 1}

{1, 2, 3} गलत: जड़ 1 बन जाती, 2 नहीं। {2, 1, 3} और {2, 3, 1} दोनों यही आकार देते हैं।

---

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

इनपुट: अलग-अलग पूर्णांक मानों वाले बाइनरी सर्च ट्री की जड़। पेड़ खाली बीएसटी में ऐरे के तत्वों को बाएँ से दाएँ डालकर बना।

आउटपुट: सभी ऐरे (मानों की सूची) जो क्रम से डालने पर ठीक यही पेड़ बनाएँ।

नियम:

• मान अलग-अलग (बराबर कुंजी नहीं)।
• मानक बीएसटी इंसर्ट: छोटा हो तो बाएँ, बड़ा हो तो दाएँ, पहले null बच्चे पर जोड़ो।
• मानों के अनुक्रम लौटाओ, नोड संदर्भ नहीं।
• खाली पेड़: एक खाली अनुक्रम साफ शिक्षण विकल्प है (कुछ न बनाने का एक तरीका)।

नोड का आकार:

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

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

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

• सिर्फ अलग मान? (इस समस्या में हाँ।)
• पेड़ बदलना? (ज़रूरत नहीं। सिर्फ संरचना पढ़ो।)
• छापना या संग्रह लौटाना? (सूचियों की List लौटाना जाँच में आसान।)
• पेड़ null हो तो? (एक खाली सूची ठीक।)

---

३. पहले सोचो

हर वैध ऐरे में क्या सच होना चाहिए?

१. जड़ पहले। कोई और मान पहले आए तो वही जड़ बन जाता। २. बाएँ उप-पेड़ का आपसी क्रम उसी उप-पेड़ से तय होता है। बाईं सभी सूचियाँ उसी उप-पेड़ के वैध इंसर्शन क्रम हों। ३. दाएँ उप-पेड़ के लिए भी वही। ४. बाएँ और दाएँ बुन सकते हैं जब तक दोनों आपसी क्रम सुरक्षित रहें। यही वीव है (ऐसा फेंटना जो हर गड्डी का क्रम रखे)।

कुछ लोग अनुमान लगाते हैं "सभी बाएँ नोड सभी दाएँ से पहले।" वह सिर्फ एक वीव है। जड़ 50 के बाद 20 फिर 60, या 60 फिर 20, दोनों 50 के सही तरफ़ गिरते हैं।

रिकर्शन का आकार

नोड n के लिए:

१. n.left के सभी अनुक्रम रिकर्सिव निकालो → leftSeqs। २. n.right के सभी अनुक्रम निकालो → rightSeqs। ३. हर जोड़े (L, R) पर L और R को सभी तरीकों से बुनो, फिर हर वीव के आगे n.val लगाओ। ४. आधार: null नोड एक खाली सूची देता है ताकि बच्चा न हो तो भी वीव चले।

"वीव" का मतलब

दो सूचियों को बुनना, हर सूची का आंतरिक क्रम बचाकर।

उदाहरण:

• first = {1, 2}
• second = {3, 4}

वीव:

परिणाम
{1, 2, 3, 4}
{1, 3, 2, 4}
{1, 3, 4, 2}
{3, 1, 2, 4}
{3, 1, 4, 2}
{3, 4, 1, 2}

गिनती जाँच: लंबाइयाँ a और b हों तो वीव की संख्या C(a+b, a) (पहली सूची के स्थान चुनो; बाकी दूसरी को)।

वीव का रिकर्सिव विचार:

• कोई सूची खाली हो तो दोनों का शेष मौजूदा प्रीफ़िक्स में जोड़कर परिणाम रखो।
• नहीं तो दो शाखाएँ: first का सिर प्रीफ़िक्स में लो, या second का। रिकर्स करो। म्यूटेशन वापस करो ताकि भाई कॉल मूल सूचियाँ देखें।

LinkedList से सिर हटाना-वापस लगाना सस्ता पड़ता है। पूरा अनुक्रम रखते समय प्रीफ़िक्स क्लोन करो ताकि बाद की म्यूटेशन पुराने जवाब न बदलें।

दो रिकर्सिव काम, अलग रखो

allSequences उप-पेड़ अनुक्रम सेट बनाता है और जड़ आगे लगाता है।

weaveLists सिर्फ दो सूचियाँ मिलाता है।

एक फ़ंक्शन में दोनों चिंताएँ मत मिलाओ। allSequences से बुलाते समय वीव पर भरोसा रखो। वीव लिखते समय सूची वापस लगाने पर भरोसा रखो।

---

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

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class BstSequences {

    public List<LinkedList<Integer>> allSequences(TreeNode node) {
        List<LinkedList<Integer>> result = new ArrayList<>();

        if (node == null) {
            result.add(new LinkedList<>());
            return result;
        }

        LinkedList<Integer> prefix = new LinkedList<>();
        prefix.add(node.val);

        List<LinkedList<Integer>> leftSeq = allSequences(node.left);
        List<LinkedList<Integer>> rightSeq = allSequences(node.right);

        for (LinkedList<Integer> left : leftSeq) {
            for (LinkedList<Integer> right : rightSeq) {
                List<LinkedList<Integer>> weaved = new ArrayList<>();
                weaveLists(left, right, weaved, prefix);
                result.addAll(weaved);
            }
        }
        return result;
    }

    /**
     * Weave first and second in all ways that keep relative order inside each list.
     * Mutates first/second/prefix during recursion, then restores them.
     */
    void weaveLists(
            LinkedList<Integer> first,
            LinkedList<Integer> second,
            List<LinkedList<Integer>> results,
            LinkedList<Integer> prefix) {

        if (first.isEmpty() || second.isEmpty()) {
            LinkedList<Integer> complete = new LinkedList<>(prefix);
            complete.addAll(first);
            complete.addAll(second);
            results.add(complete);
            return;
        }

        // take head of first
        int headFirst = first.removeFirst();
        prefix.addLast(headFirst);
        weaveLists(first, second, results, prefix);
        prefix.removeLast();
        first.addFirst(headFirst);

        // take head of second
        int headSecond = second.removeFirst();
        prefix.addLast(headSecond);
        weaveLists(first, second, results, prefix);
        prefix.removeLast();
        second.addFirst(headSecond);
    }
}

नमूना पेड़ 2 / 1 3 का चलना:

१. बायाँ बच्चा 1 पत्ती: अनुक्रम {{1}}। २. दायाँ बच्चा 3 पत्ती: अनुक्रम {{3}}। ३. {1} और {3} का वीव: {1,3} और {3,1}। ४. जड़ 2 आगे: {2,1,3} और {2,3,1}।

बड़ा रेखाचित्र: जड़ 50, बायाँ उप-पेड़ 20 पर, दायाँ 60 पर। रिकर्स करो जब तक हर उप-पेड़ अपना अनुक्रम सेट लौटाए। हर बाएँ अनुक्रम को हर दाएँ से बुनो, फिर हर वीव के आगे 50 लगाओ। वही पेड़ का पूरा जवाब है।

कम से कम इस्तेमाल:

TreeNode root = new TreeNode(2);
root.left = new TreeNode(1);
root.right = new TreeNode(3);

List<LinkedList<Integer>> seqs = new BstSequences().allSequences(root);
// [[2, 1, 3], [2, 3, 1]]

---

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

हिस्सा	लागत नोट
अनुक्रमों की संख्या	कॉम्बिनेटोरियल बढ़ सकती है। सबसे खराब: एक तरफ़ पतली श्रृंखला, दूसरी तरफ़ बड़ा मुक्त वीव।
लंबाई a, b का वीव	C(a+b, a) परिणाम; हर परिणाम क्लोन/जोड़ पर ओ(a+b)।
allSequences	हर नोड पर बाएँ×दाएँ गिनती × वीव लागत।
अतिरिक्त स्थान	आउटपुट आकार हावी। रिकर्शन गहराई पेड़ पर ओ(एच) और वीव पर ओ(a+b)।

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

समय आउटपुट-संवेदी है। जो अनुक्रम लौटाओगे उन्हें छूना पड़ेगा। ओ(एन) मत कहो जब तक एन बहुत छोटा और पेड़ शुद्ध श्रृंखला न हो (अक्सर एक ही अनुक्रम)।

---

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

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

• null जड़ → एक खाली अनुक्रम (या खाली परिणाम सूची; बोल दो)।
• एक नोड → सिर्फ {val}।
• सिर्फ बाएँ या सिर्फ दाएँ → असली इंटरलीव नहीं; वीव "जड़ के बाद भरा तरफ़" बन जाता है।
• छोटा संतुलित पेड़ → जड़ के बाद क्लासिक दो-तरफ़ा वीव (नमूना 2/1/3)।
• गहरा बायाँ, गहरा दायाँ → बहुत वीव; स्टैक और क्लोनिंग देखो।

आम गलतियाँ:

१. सभी बाएँ को सभी दाएँ से पहले मजबूर करना। आधे (या अधिक) वैध क्रम छूट जाते हैं। २. जड़ पहले भूलना। गैर-जड़ से शुरू कोई अनुक्रम इस पेड़ के लिए अमान्य। ३. उप-पेड़ का आपसी क्रम तोड़ना। बाएँ को 20 फिर 10 चाहिए तो वीव 10 को 20 से आगे नहीं रख सकता। ४. रिकर्शन के बाद सूचियाँ वापस न लगाना। बिना अनडू साझा LinkedList भाई शाखाएँ खराब करता है। ५. परिणाम रखते समय साझा प्रीफ़िक्स बदलना। results.add से पहले क्लोन करो। ६. सभी नोड की परमुटेशन गिनकर हर इंसर्ट जाँचना। छोटे एन पर चलता है, समस्या की भावना नहीं, संरचित वीव से बहुत धीमा।

इंटरव्यू में तेज़ स्व-जाँच: लौटाया एक ऐरे लो, नए बीएसटी में डालो, आकार मिलाओ। जल्दी बाएँ-दाएँ बुनने वाला वीव भी देखो।

---

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

बीएसटी सीक्वेंसेस पूछता है "कौन से इंसर्शन क्रम ठीक यही बीएसटी फिर बनाएँ?":

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

तीन-नोड नमूना खींच सको, दोनों जवाब लिख सको, और बता सको जड़ 2 पर {1,2,3} अवैध क्यों है, तो समस्या ४.९ तुम्हारी है।

---

सीरीज़

• गाइड: सीटीसीआई सीरीज़ गाइड
• पिछला: फ़र्स्ट कॉमन ऐन्सेस्टर
• अगला: चेक सबट्री