फर्स्ट कॉमन ऐंसेस्टर: पैरेंट लिंक के बिना एलसीए (जावा)

टीएल;डीआर

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

पारिवारिक वृक्ष में दो लोग। दोनों से ऊपर, सबसे पुरानी जड़ की ओर चलो। दोनों रास्तों पर पहली बार जो व्यक्ति मिले, वह साझा पूर्वज है। पहला साझा पूर्वज सबसे गहरा वाला होता है: दोनों के जितना पास हो सके, जड़ तभी जब जड़ ही एकमात्र साझा बिंदु हो।

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

---

१. ट्री की उपमा

कंपनी का संगठन चार्ट बाइनरी ट्री जैसा सोचो। हर बॉक्स के नीचे ज़्यादा से ज़्यादा दो रिपोर्ट। ऐलिस और बॉब चार्ट में कहीं बैठे हैं। सीईओ से सबसे दूर (ऐलिस-बॉब के सबसे पास) वाला साझा मैनेजर ही फर्स्ट कॉमन ऐंसेस्टर है।

ज़रूरी फ़र्क:

• कई इंटरव्यू बयानों में एक्स का पूर्वज में एक्स खुद भी गिना जाता है। अगर बॉब ऐलिस के नीचे रिपोर्ट करता है, तो ऐलिस उत्तर हो सकती है।
• पहला / सबसे निचला मतलब ट्री में सबसे गहरा, बाएँ-से-दाएँ घूमने में "पहला" नहीं।
• यह बीएसटी नहीं। मान के क्रम से बाएँ-दाएँ नहीं चुन सकते। सिर्फ संरचना: बायाँ बच्चा, दायाँ बच्चा, और अगर इंटरव्यूअर दे तो पैरेंट पॉइंटर।

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

---

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

लक्ष्य: बाइनरी ट्री की जड़ और दो नोड p व q (जो ट्री में हों भी या न हों) दिए हों; उनका फर्स्ट कॉमन ऐंसेस्टर नोड लौटाओ, या null अगर नाम न बता सको।

ज़रूरी सीमाएँ:

• बाइनरी ट्री, जरूरी नहीं बीएसटी।
• हर पूर्वज की सूची जमा न करो (क्लासिक "अतिरिक्त नोड लिस्ट न रखो" स्वाद)।
• TreeNode पर पैरेंट न हो तो बेहतर।
• स्पष्ट करो: क्या p या q उत्तर हो सकते हैं जब एक दूसरे के नीचे हो (आमतौर पर हाँ)।
• स्पष्ट करो: एक नोड ट्री में न हो तो क्या (आमतौर पर null)।

नोड का रूप (बिना पैरेंट):

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

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

छोटा उदाहरण

        3
       / \
      5   1
     / \ / \
    6  2 0  8
      / \
     7   4

• 6 और 4 का एफसीए 5 है।
• 5 और 4 का एफसीए 5 है (नोड खुद को ढकता है)।
• 6 और 8 का एफसीए 3 है।

---

३. पहले सोचो

वैकल्पिक: पैरेंट लिंक, लिस्ट इंटरसेक्शन जैसी चढ़ाई

अगर हर नोड में parent हो:

१. p और q की गहराई जड़ तक चढ़कर नापो। २. गहरे नोड को ऊपर उठाओ जब तक दोनों एक ही गहराई पर न आ जाएँ। ३. दोनों को एक-एक कदम ऊपर ले जाओ जब तक पॉइंटर न मिलें। वही फर्स्ट कॉमन ऐंसेस्टर।

समय ओ(डी), जहाँ डी गहरे नोड की गहराई। अतिरिक्त जगह ओ(१)। वही विचार जो सीटीसीआई २.७ इंटरसेक्शन में: दो रास्ते जड़ की ओर एक साझा प्रत्यय बाँटते हैं।

जब एपीआई पहले से पैरेंट रखती हो तो उपयोगी। अगर इंटरव्यूअर कहे "नोड सिर्फ बच्चों को जानते हैं" तो मुख्य रास्ता नहीं।

बिना पैरेंट का सरल तरीका: covers से तरफ़ जाँच

जड़ से पूछो: "क्या बायाँ सबट्री p को ढकता है?" और "क्या बायाँ q को ढकता है?"

• अलग जवाब: p और q इस नोड के नीचे अलग तरफ़, तो यही नोड एफसीए।
• एक ही तरफ़: सिर्फ उसी तरफ़ रिकर्स करो।

सही है, पर हर covers सबट्री घूमता है और बार-बार बुलाया जाता है। संतुलित ट्री पर भी ओ(एन), पर स्थिरांक खराब क्योंकि वही नोड्स बार-बार स्कैन होते हैं।

पसंदीदा: एक रिकर्शन, स्टेटस लौटाओ

ट्री एक बार ही घूमना है। एक रिकर्सिव हेल्पर छोटा स्टेटस ऑब्जेक्ट लौटाता है:

• एक node उम्मीदवार (p, q, असली पूर्वज, या null)
• झंडा isAncestor जो कहता है "यह node पहले से असली फर्स्ट कॉमन ऐंसेस्टर है"

ऊपर आने वाले नियम:

१. खाली सबट्री → (null, false) (कोड स्टेटस)। २. बाएँ और दाएँ दोनों गैर-नूल नोड लौटाएँ → मौजूदा जड़ साझा पूर्वज (isAncestor = true)। ३. मौजूदा जड़ p या q है, और दूसरा लक्ष्य किसी सबट्री में मिला → मौजूदा जड़ असली पूर्वज। ४. मौजूदा जड़ p या q है, और दूसरा नीचे नहीं मिला → यह जड़ isAncestor = false के साथ लौटाओ (सिर्फ "एक लक्ष्य मिला")। ५. सिर्फ एक तरफ़ कुछ मिला → वही परिणाम ऊपर भेजो (जब तक कदम ३ लागू न हो)। ६. किसी बच्चे ने पहले ही isAncestor = true लगाया हो तो शॉर्ट-सर्किट करके वही ऊपर भेजो।

झंडा क्यों? बिना इसके "मुझे p मिला पर q नहीं" और "p, q के नीचे है" एक जैसे लगते हैं अगर सिर्फ एक पॉइंटर लौटाओ। झंडा असली एलसीए को आंशिक खोज से अलग करता है। शीर्ष पर अगर isAncestor गलत है तो null (गायब नोड या अधूरी जोड़ी)।

यही समाधान पहले कोड और समझाना है।

---

४. जावा समाधान (बिना पैरेंट)

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

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

/** एक रिकर्सिव पास का स्टेटस। */
class Result {
    TreeNode node;
    boolean isAncestor;

    Result(TreeNode node, boolean isAncestor) {
        this.node = node;
        this.isAncestor = isAncestor;
    }
}

class FirstCommonAncestor {

    /**
     * root के नीचे p और q का फर्स्ट कॉमन ऐंसेस्टर, या null अगर
     * पूरी तरह मौजूद वैध जोड़ी न हो (जैसे एक नोड गायब)।
     */
    TreeNode commonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Result r = helper(root, p, q);
        return r.isAncestor ? r.node : null;
    }

    private Result helper(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return new Result(null, false);
        }

        // एक ही नोड दो बार (p == q == root)
        if (root == p && root == q) {
            return new Result(root, true);
        }

        Result left = helper(root.left, p, q);
        if (left.isAncestor) {
            return left; // नीचे पहले से लॉक
        }

        Result right = helper(root.right, p, q);
        if (right.isAncestor) {
            return right;
        }

        if (left.node != null && right.node != null) {
            // p और q अलग सबट्री में
            return new Result(root, true);
        }

        if (root == p || root == q) {
            // यहाँ एक लक्ष्य; असली पूर्वज तभी जब दूसरा नीचे मिला
            boolean foundOther = left.node != null || right.node != null;
            return new Result(root, foundOther);
        }

        // जो तरफ़ नोड मिला वही ऊपर (या null)
        TreeNode bubble = left.node != null ? left.node : right.node;
        return new Result(bubble, false);
    }
}

नमूना ट्री पर p = 6, q = 4 (दोनों 5 के नीचे) का घूमना:

कदम	फोकस	क्या ऊपर आता है	नोट
१	पत्ती 6	node=6, false	जड़ p से मेल
२	2 के सबट्री में 4	node=4, false	2 का दायाँ
३	नोड 2	4 ऊपर	p/q नहीं
४	नोड 5: बाएँ 6, दाएँ 4	node=5, true	दोनों तरफ़ गैर-नूल
५	जड़ 3	बायाँ पहले से isAncestor	शॉर्ट-सर्किट, 5 लौटा

अगर q ट्री के बाहर का नोड हो, तो p isAncestor = false के साथ ऊपर आ सकता है, और सार्वजनिक विधि null लौटाती है। झंडा यहीं काम आता है।

---

५. वैकल्पिक: पैरेंट पर चढ़ना

जब TreeNode में parent हो:

class TreeNodeWithParent {
    int val;
    TreeNodeWithParent left;
    TreeNodeWithParent right;
    TreeNodeWithParent parent;
}

TreeNodeWithParent commonAncestorWithParents(
        TreeNodeWithParent p, TreeNodeWithParent q) {
    int delta = depth(p) - depth(q);
    TreeNodeWithParent first = delta > 0 ? q : p;   // उथला
    TreeNodeWithParent second = delta > 0 ? p : q;  // गहरा
    second = goUpBy(second, Math.abs(delta));

    while (first != second && first != null && second != null) {
        first = first.parent;
        second = second.parent;
    }
    return (first == null || second == null) ? null : first;
}

int depth(TreeNodeWithParent node) {
    int d = 0;
    while (node != null) {
        node = node.parent;
        d++;
    }
    return d;
}

TreeNodeWithParent goUpBy(TreeNodeWithParent node, int delta) {
    while (delta > 0 && node != null) {
        node = node.parent;
        delta--;
    }
    return node;
}

इंटरव्यू में स्टेटस वाली रिकर्सिव सॉल्यूशन के बाद यह बताओ: "अगर पैरेंट हों तो गहराई बराबर करके साथ चढ़ो; लिस्ट इंटरसेक्शन जैसा विचार।" फिर साधारण बाइनरी ट्री के लिए बिना-पैरेंट संस्करण पर लौटो।

---

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

तरीका	समय	अतिरिक्त जगह	पैरेंट चाहिए?
पैरेंट चढ़ाई (गहराई मिलाओ)	ओ(डी)	ओ(१)	हाँ
बार-बार covers + शाखा	ओ(एन) (खराब स्थिरांक)	ओ(एच) स्टैक	नहीं
एक रिकर्शन + Result स्टेटस	ओ(एन)	ओ(एच) स्टैक	नहीं

एन = ट्री के नोड्स, डी = गहरे नोड की गहराई, एच = ऊँचाई (रिकर्शन स्टैक)। बिना पैरेंट या अतिरिक्त इंडेक्स के सबसे खराब ओ(एन) नहीं जीतते, क्योंकि गायब नोड लगभग सब जगह देखने को मजबूर करता है।

---

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

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

• एक नोड दूसरे का पूर्वज → उत्तर ऊपर वाला (isAncestor तब true जब दूसरा नीचे मिले)।
• p == q → वही नोड (अगर मौजूद)।
• एक या दोनों गायब → शीर्ष पर isAncestor == false से null।
• जड़ ही एकमात्र साझा पूर्वज → लक्ष्य जड़ के अलग तरफ़ (या एक जड़ है और दूसरा नीचे)।
• खाली ट्री / null जड़ → null।
• बीएसटी नहीं → दिशा तय करने के लिए कभी val की तुलना न करो।

आम गलतियाँ:

१. पहली आंशिक खोज को एलसीए मान लेना बिना झंडे या "दोनों मौजूद" स्कैन के। २. जड़-से-नोड पूरे पथ सूचियों में रखना जब समस्या वह शैली टालने को कहे (वार्म-अप ठीक; कहकर आगे बढ़ो)। ३. साधारण बाइनरी ट्री पर बीएसटी तर्क लगाना। ४. भूलना कि p या q उत्तर हो सकते हैं जब एक दूसरे को ढके। ५. ट्री या पैरेंट बदलना जब सिर्फ पढ़ने वाला घूमना काफी था।

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

// उदाहरण ट्री जड़ 3 से बनाओ ... फिर:
TreeNode ans = new FirstCommonAncestor().commonAncestor(root, node6, node4);
// ans.val == 5

---

८. दोस्त को समझाओ

साधारण बाइनरी ट्री पर फर्स्ट कॉमन ऐंसेस्टर:

१. सबसे गहरा नोड जिसके सबट्री में दोनों लक्ष्य हों (नोड अपने सबट्री में गिना जाता है)। २. पैरेंट के साथ: गहराई बराबर करो, साथ चढ़ो जब तक पॉइंटर न मिलें। ३. बिना पैरेंट (पसंदीदा): एक डीएफएस जो स्टेटस लौटाए (node + isAncestor)। ४. दोनों बच्चे खोज बताएँ → मौजूदा नोड एलसीए। ५. मौजूदा नोड एक लक्ष्य है और दूसरा नीचे मिला → मौजूदा एलसीए। ६. आंशिक खोज बिना true झंडे के → ऊपर भेजो; शीर्ष पर पुष्टि न हो तो null।

अगर नमूना ट्री खींच सको, बाएँ-दाएँ हिट चिह्नित कर सको, और झंडा क्यों है समझा सको, तो समस्या ४.८ तुम्हारी है।

---

सीरीज़

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