दो बाइनरी ट्री की समानता जाँचने का तेज़ और साफ तरीका

दो बाइनरी ट्री की संरचना व मान समानता O(n) समय, O(h) स्थान में कैसे जाँचें। Python में अनुकूलित रिकर्सिव तरीका, इटरेटिव विकल्प, शुरुआती एग्जिट, सर्वोत्तम टिप्स.

दो बाइनरी ट्री की संरचना और मानों की समानता की तुलना पहली नज़र में ऐसा काम लगता है, जहाँ कुछ चतुर तरकीबें अतिरिक्त प्रदर्शन निकाल सकती हैं। लेकिन व्यवहार में, सीधी और साधारण रिकर्सिव विधि ही पहले से सबसे तेज़ है, और एक छोटे से सुधार के साथ यह एक साथ सुरुचिपूर्ण और कुशल बन जाती है।

समस्या की रूपरेखा

काम यह जाँचना है कि क्या दो बाइनरी ट्री आकार और नोड मानों—दोनों में—एकदम समान हैं। एक सामान्य रिकर्सिव तरीका दोनों पेड़ों के नोड्स को साथ‑साथ विजिट करता है और पहले ही असमानता पर रुक जाता है। समय जटिलता O(n) है, क्योंकि हर नोड को एक बार देखना पड़ सकता है, और सहायक स्थान O(h) है, जहाँ h ट्री की ऊँचाई है।

class Node:
    def __init__(self, val=None, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
def same_tree(u: Node, v: Node) -> bool:
    if u is None and v is None:
        return True
    return (u is not None and v is not None) and (u.val == v.val) and \
        same_tree(u.left, v.left) and same_tree(u.right, v.right)
x = Node(1)
y = Node(1)
print(same_tree(x, y))

असल में क्या हो रहा है

यहाँ कोई भी एल्गोरिद्म O(n) से तेज़ नहीं हो सकता, क्योंकि दोनों पेड़ों के मेल खाने की पक्की तस्दीक के लिए कम से कम हर नोड पर एक नज़र डालनी ही पड़ेगी। यही निचली सीमा रिकर्सिव समाधान को समय के लिहाज़ से सैद्धांतिक रूप से इष्टतम बनाती है। मेमोरी की बात करें तो रिकर्शन O(h) स्टैक फ्रेम लेता है, जो उस डेप्थ‑फर्स्ट तुलना के लिए इष्टतम है जो ट्री के आकार का अनुसरण करती है। शॉर्ट‑सर्किटिंग यह सुनिश्चित करती है कि जैसे ही अंतर मिले, ट्रैवर्सल तुरंत रुक जाए।

यहाँ एक छोटा‑सा सुधार उपयोगी है। आइडेंटिटी चेक तब गहरी जाँच से बचा लेता है जब दोनों रेफरेंस बिल्कुल उसी नोड ऑब्जेक्ट की ओर इशारा कर रहे हों, और शुरुआती नकारात्मक जाँच असमानता के मामलों के लिए हॉट पाथ को साफ रखती है।

अनुकूलित रिकर्सिव संस्करण

def trees_match(a, b):
    if a is b:
        return True
    if not a or not b or a.val != b.val:
        return False
    return trees_match(a.left, b.left) and trees_match(a.right, b.right)

समय अभी भी O(n) और स्थान O(h) ही रहता है। आइडेंटिटी टेस्ट None के केस और एक‑ही रेफरेंस दोनों को तुरंत संभाल लेता है। संरचना या मान के मेल न खाने पर शुरुआती रिटर्न संभव होते ही काम रोक देता है। व्यवहार में, इससे अनावश्यक कॉल्स घटती हैं और बिना अतिरिक्त बुककीपिंग के कोड सधा हुआ रहता है।

क्या इससे तेज़ या अधिक मेमोरी‑कुशल विकल्प हैं

स्पष्ट स्टैक या क्यू पर आधारित विकल्प संभव हैं, पर वे आसिम्प्टोटिक्स को नहीं बदलते। इटरेटिव डेप्थ‑फर्स्ट या ब्रेड्थ‑फर्स्ट ट्रैवर्सल भी O(n) समय में चलता है। कॉल स्टैक की जगह हीप पर स्टैक/क्यू का इस्तेमाल होता है, इसलिए सहायक स्थान का प्रोफाइल बदलकर ट्रैवर्सल फ्रंटियर के अनुपात में रहता है। किसी गति का चमत्कार नहीं मिलता; फर्क बस काम करने की शैली और यह है कि स्टेट कहाँ रखा गया है।

व्यावहारिक पहलू चुनाव को प्रभावित करते हैं। एक नजरिया कहता है कि रिकर्सिव रूप साफ है, ओवरहेड कम है, और ट्री की संरचना का स्वाभाविक अनुसरण करके बेहतर कैश लोकैलिटी देता है। दूसरा नजरिया असली सिस्टमों में रिकर्शन डेप्थ को लेकर भरोसे की चिंताओं पर जोर देता है और ऐसे इटरेटिव तरीकों को प्राथमिकता देता है जो कॉल स्टैक लिमिट पर निर्भर न हों। आपकी सीमाओं पर निर्भर करते हुए दोनों बातें सही हो सकती हैं।

ऐसा फ़ंक्शन, जो आपको कॉल स्टैक का आकार परखने और समायोजित करने पर मजबूर करे, उस फ़ंक्शन जितना उपयोगी नहीं है जो बस भरोसेमंद तरीके से काम कर दे। असल जिंदगी में लोग उसे कॉल करेंगे और उम्मीद करेंगे कि वह चले; वरना वह ऐसी लैंडमाइन बन जाती है जो अचानक फट पड़ती है।

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

जब आपको पक्का न हो कि आपके ट्री उथले हैं, तो इटरेटिव संस्करण बेहतर है। प्रोडक्शन कोड में आप बाइनरी ट्री पर तभी रिकर्सिव प्रोसेसिंग करेंगे जब वह रेड‑ब्लैक या AVL की तरह बैलेंस्ड हो।

इन दृष्टिकोणों से एक सरल नियम बनता है। अगर आपके ट्री बैलेंस्ड हैं या उथले होने की गारंटी है, तो रिकर्सिव तरीका इष्टतम भी है और संभालना भी आसान। अगर ट्री की गहराई अंजान है या बहुत बढ़ सकती है, तो इटरेटिव तरीका रिकर्शन डेप्थ से जुड़े अप्रिय आश्चर्यों से बचाता है।

यह क्यों मायने रखता है

कई सिस्टमों के हॉट पाथ पर ट्री तुलना आती है। यह जानना कि O(n) ही ऊपरी सीमा है, आपको काल्पनिक स्पीडअप्स का पीछा करने से रोकता है, और O(h) स्टैक व्यवहार को पहचानना आपको अनुमान के बजाय संचालन जोखिम के आधार पर रिकर्शन और इटरेशन में चुनने देता है। रिकर्सिव संस्करण में छोटे‑छोटे सुधार—जैसे आइडेंटिटी चेक और शुरुआती एग्जिट—बिना कोड को जटिल बनाए व्यावहारिक लाभ दिलाते हैं।

मुख्य बातें

जब आप ट्री की गहराई को नियंत्रित कर सकते हैं या उस पर सीमा तय कर सकते हैं, तो शुरुआती एग्जिट के साथ रिकर्सिव समाधान अपनाएँ। समय के लिहाज़ से यह पहले से इष्टतम है, बैलेंस्ड ट्री के लिए स्थान‑कुशल है, और सुखद रूप से संक्षिप्त है। जब गहराई अनबाउंडेड हो या स्टैक लिमिट चिंता का विषय हो, तो इटरेटिव स्टैक या क्यू पर स्विच करें। दोनों ही तरीकों में O(n) समय की अपेक्षा रखें; सटीक संरचनात्मक और मान समानता के लिए यही सिर्फ पर्याप्त नहीं, बल्कि सर्वोत्तम संभव है।