कोडिंग इंटरव्यू: एक बाइनरी ट्री का लोएस्ट कॉमन एन्सेस्टर (LCA) खोजें

समस्या और दायरा

एक आर्बिट्रेरी बाइनरी ट्री और उसमें दो अलग-अलग नोड्स p और q दिए जाने पर, उनका लोएस्ट कॉमन एन्सेस्टर (LCA) लौटाएं। एक नोड स्वयं का एन्सेस्टर होता है। LCA वह सबसे गहरा नोड है जिसके सब-ट्री में दोनों टारगेट शामिल होते हैं, इसलिए यदि p, q का एन्सेस्टर है, तो उत्तर स्वयं p ही है।

चार विवरण मूल अनुबंध (बेस कॉन्ट्रैक्ट) को परिभाषित करते हैं: ट्री बाइनरी सर्च ट्री (BST) नहीं है; इनपुट वैल्यूज के बजाय नोड ऑब्जेक्ट्स की पहचान करते हैं; अलग-अलग नोड्स का मान समान हो सकता है; और p तथा q दोनों का ट्री में होना सुनिश्चित है। वैल्यूज की तुलना करना चुपचाप उस अनुबंध का उल्लंघन करता है। उपस्थिति की गारंटी हटाने के बाद बेस रिकर्सन का पुन: उपयोग करने से एक सूक्ष्म फॉल्स पॉजिटिव (गलत परिणाम) भी उत्पन्न होता है।

a
      /   \
     b     c
    / \   / \
   d   e f   g
        \
         h

यहाँ, LCA(d, h) = b, LCA(b, h) = b, और LCA(e, f) = a। यह प्रश्न उन सॉफ्टवेयर इंजीनियर्स के लिए है जिनसे ट्री ट्रैवर्सल, रिकर्सिव सिमेंटिक्स और जटिलता को समझने की अपेक्षा की जाती है। बेस केस में एक क्वेरी पूछी जाती है। असीमित गहराई, अनुपस्थित टारगेट, पेरेंट पॉइंटर्स, या एक ही स्टैटिक ट्री पर कई क्वेरी ऐसे फॉलो-अप प्रतिबंध हैं जो सबसे अच्छे समाधान को बदल देते हैं।

इंटरव्यूअर क्या मूल्यांकन कर रहा है

पहला उपयोगी अवलोकन "लोएस्ट" को संरचना में बदल देता है: उत्तर रूट-से-p और रूट-से-q पाथ पर अंतिम कॉमन नोड है। दोनों पाथ को स्टोर करना सही है, लेकिन अनावश्यक है। एक अधिक स्पष्ट निष्कर्ष हर सब-ट्री से तीन स्थितियों में से एक की रिपोर्ट करने के लिए कहता है: कोई टारगेट नहीं मिला, एक टारगेट मिला, या वह बिंदु जहाँ दोनों टारगेट पहले ही मिल चुके हैं।

एक मजबूत उत्तर रिकर्सिव रिटर्न वैल्यू को सटीक रूप से परिभाषित करता है। node पर रूट वाले सब-ट्री के लिए, फ़ंक्शन निम्नलिखित लौटाता है:

• null जब सब-ट्री में न तो p हो और न ही q;
• p या q जब एक खोजे गए टारगेट को ऊपर प्रचारित (propagate) किया जाना हो;
• एक अन्य नोड जब वह नोड इस सब-ट्री के अंदर पहले से ही LCA हो।

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

अनुबंध का जाल महत्वपूर्ण है। यदि q अनुपस्थित है, तो बेस एल्गोरिदम p लौटा सकता है; यह यह सिद्ध नहीं करता कि दोनों टारगेट मौजूद हैं। एक बार गारंटी हटा दिए जाने के बाद, रिकर्सिव परिणाम को एक मैच काउंट की आवश्यकता होती है। n नोड्स और h ऊँचाई वाले ट्री के लिए, एक क्वेरी सबसे खराब स्थिति में हर नोड पर जाती है, इसलिए समय O(n) है और रिकर्सिव स्टैक O(h) है। एक तिरछे (skewed) ट्री में, h = n, और कॉल स्टैक एल्गोरिदम के काम के बजाय विफलता का कारण बन सकता है।

पहले स्पष्ट किए जाने वाले प्रश्न

• क्या इनपुट नोड रेफरेंस हैं या वैल्यूज? रेफरेंस डुप्लिकेट वैल्यूज की अनुमति देते हैं, इसलिए node === p से तुलना करें। वैल्यू लुकअप केवल तभी मान्य है जब विशिष्टता अनुबंध का हिस्सा हो।
• क्या दोनों टारगेट का मौजूद होना और अलग होना सुनिश्चित है? बेस रिकर्सन उपस्थिति पर निर्भर करता है। यदि कोई भी अनुपस्थित हो सकता है, तो एक मैच काउंट भी लौटाएं। यदि p === q की अनुमति है, तो परिभाषित करें कि क्या उस ऑब्जेक्ट को एक बार खोजना पर्याप्त है।
• क्या यह एक आर्बिट्रेरी बाइनरी ट्री है या बाइनरी सर्च ट्री? एक आर्बिट्रेरी ट्री को संरचनात्मक खोज की आवश्यकता होती है। एक BST एक पाथ पर की (key) क्रम का पालन कर सकता है, लेकिन डुप्लिकेट की और रेफरेंस पहचान उस शॉर्टकट को अमान्य कर सकती है।
• अधिकतम नोड संख्या और ऊँचाई क्या है? एक संतुलित ट्री में O(log n) रिकर्सन गहराई होती है। 100,000-नोड वाली श्रृंखला में रनटाइम स्टैक ओवरफ्लो से बचने के लिए एक स्पष्ट स्टैक और पेरेंट मैप की आवश्यकता होती है।
• एक ही स्टैटिक ट्री पर कितनी क्वेरी की जाएंगी? एक सिंगल क्वेरी सीधे DFS का समर्थन करती है। कई क्वेरी O(log n) क्वेरी के लिए गहराई और 2^k एन्सेस्टर्स की प्रीकंप्यूटिंग को उचित ठहरा सकती हैं।
• क्या नोड्स में पहले से ही पेरेंट पॉइंटर्स हैं? तब रूट से ट्रैवर्स करने की आवश्यकता नहीं है। गहराइयों को संरेखित करें और एक साथ ऊपर चलें, या एक एन्सेस्टर श्रृंखला रिकॉर्ड करें और उसका पहला प्रतिच्छेदन (intersection) खोजें।

30-सेकंड उत्तर ढांचा

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

चरण-दर-चरण समाधान

चरण 1: एक सही पाथ बेसलाइन स्थापित करें

सबसे सीधा तरीका रूट-से-p और रूट-से-q पाथ खोजना है, रूट से उनकी तुलना करना है, और उनके अंतिम साझा नोड को वापस करना है। यह परिभाषा को स्पष्ट रूप से समझाता है और स्वाभाविक रूप से मान्य करता है कि दोनों टारगेट मौजूद हैं। दो DFS पास अभी भी O(n) समय लेते हैं, जबकि पाथ और रिकर्सन O(h) स्पेस का उपयोग करते हैं। एक कार्यान्वयन जो प्रत्येक खोजे गए नोड को बनाए रखता है, O(n) स्पेस तक बढ़ सकता है।

अनावश्यक बात यह है कि दोनों खोजें एक बड़े साझा प्रीफिक्स को पार करती हैं। केवल वही जानकारी आवश्यक है जो एक सब-ट्री अपने पेरेंट को रिपोर्ट करता है, इसलिए दो पाथ को एक पोस्टऑर्डर ट्रैवर्सल में संकुचित किया जा सकता है।

चरण 2: रिटर्न वैल्यू को परिभाषित करें और एक बार ट्रैवर्स करें

interface TreeNode {
  value: number
  left: TreeNode | null
  right: TreeNode | null
}

function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (root === null || root === p || root === q) {
    return root
  }

  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)

  if (left !== null && right !== null) {
    return root
  }

  return left ?? right
}

कोड ऑब्जेक्ट पहचान की तुलना करता है और कभी भी value को नहीं पढ़ता है, इसलिए अलग-अलग नोड्स पर समान वैल्यूज सुरक्षित हैं। पोस्टऑर्डर आवश्यक है: वर्तमान नोड को यह तय करने से पहले कि क्या यह पहला मिलन बिंदु है, दोनों चाइल्ड रिपोर्ट की आवश्यकता होती है।

चरण 3: इसे एक इनवेरिएंट के साथ सिद्ध करें

node पर रूट वाले किसी भी सब-ट्री पर विचार करें, और मान लें कि दोनों रिकर्सिव कॉल रिटर्न-वैल्यू परिभाषा को संतुष्ट करते हैं।

1. यदि node नल है, तो सब-ट्री में कोई टारगेट नहीं है, इसलिए null सही है।
2. यदि node, p या q है, तो node लौटाएं। चूंकि दोनों टारगेट मौजूद हैं, यह टारगेट या तो LCA है क्योंकि इसमें दूसरा टारगेट शामिल है, या इसे किसी एन्सेस्टर को एक टारगेट की रिपोर्ट करनी होगी।
3. यदि दोनों चाइल्ड परिणाम नॉन-नल हैं, तो प्रत्येक पक्ष एक टारगेट की रिपोर्ट करता है। कोई गहरा नोड दोनों पक्षों से संबंधित नहीं है, इसलिए node सबसे गहरा कॉमन एन्सेस्टर है।
4. यदि ठीक एक पक्ष नॉन-नल है, तो वर्तमान नोड कोई नया मिलन बिंदु नहीं बनाता है। उस पक्ष का टारगेट या पूर्ण LCA ही प्रचारित करने के लिए एकमात्र मान्य परिणाम है। यदि दोनों नल हैं, तो null लौटाएं।

स्ट्रक्चरल इंडक्शन द्वारा, रूट पर लौटाया गया परिणाम पूरे ट्री का LCA होता है। यह प्रमाण उस एन्सेस्टर केस को भी कवर करता है जिसे अक्सर अनदेखा कर दिया जाता है: जब p, q का एन्सेस्टर होता है, तो p तक पहुंचना इसे नीचे से दूसरी बार q लौटाए जाने की आवश्यकता के बिना लौटा देता है।

चरण 4: वास्तविक समय और स्थान की लागत बताएं

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

सहायक स्थान (auxiliary space) रिकर्सन के लिए O(h) है। संतुलित ट्री में, h = O(log n); पूरी तरह से तिरछे ट्री में, h = n। लौटाया गया नोड रेफरेंस सहायक स्टोरेज के रूप में नहीं गिना जाता है। समाधान को O(1) स्पेस कहना कॉल स्टैक को अनदेखा करता है।

चरण 5: टारगेट गायब होने की स्थिति में अनुबंध बदलें

अस्तित्व की गारंटी के बिना, बेस फ़ंक्शन गलत परिणाम दे सकता है: यदि ट्री में केवल p आता है, तो यह p को रूट तक प्रचारित करता है। एक सुरक्षित संस्करण उम्मीदवार नोड को वास्तव में पाए गए टारगेट की संख्या से अलग करता है।

interface SearchResult {
  candidate: TreeNode | null
  matches: number
}

function lowestCommonAncestorValidated(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  function visit(node: TreeNode | null): SearchResult {
    if (node === null) {
      return { candidate: null, matches: 0 }
    }

    const left = visit(node.left)
    if (left.matches === 2) {
      return left
    }

    const right = visit(node.right)
    if (right.matches === 2) {
      return right
    }

    const self = node === p || node === q ? 1 : 0
    const matches = left.matches + right.matches + self

    return {
      candidate: matches === 2 ? node : left.candidate ?? right.candidate ?? (self ? node : null),
      matches,
    }
  }

  const result = visit(root)
  return result.matches === 2 ? result.candidate : null
}

यह संस्करण अभी भी p !== q मानता है। यदि एक ही रेफरेंस दो बार दिया जा सकता है, तो पहले अनुबंध को परिभाषित करें: उस नोड को एक बार खोजने पर matches === 2 की आवश्यकता जारी रखने के बजाय उसे वापस कर देना चाहिए। बाधाओं में बदलाव कोड परिवर्तनों से पहले होने चाहिए।

चरण 6: गहरे पेड़ों के लिए एक स्पष्ट स्टैक और पेरेंट मैप का उपयोग करें

जब ऊँचाई 100,000 के करीब पहुँच सकती है, तो एसिम्प्टोटिक रिकर्सन स्पेस अपरिवर्तित रहता है, लेकिन रनटाइम का कॉल स्टैक पहले ओवरफ्लो हो सकता है। एक स्पष्ट स्टैक के साथ ट्रैवर्स करें और तब तक parent.get(child) = node रिकॉर्ड करें जब तक कि p और q दोनों मैप में न हों। p के प्रत्येक एन्सेस्टर को एक सेट में डालें, फिर q से ऊपर की ओर चलें; पहला सेट सदस्य LCA है।

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

चरण 7: एडवरसेरियल केस के साथ सिमेंटिक्स को सत्यापित करें

कम से कम, इस मैट्रिक्स को कवर करें:

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

उच्च गुणवत्ता वाला नमूना उत्तर

"मैं पहले अनुबंध को स्पष्ट करूँगा: यह एक आर्बिट्रेरी बाइनरी ट्री है, p और q अलग-अलग नोड रेफरेंस हैं जिनका होना सुनिश्चित है, और वैल्यूज दोहराई जा सकती हैं। इसलिए मेरा कोड वैल्यूज की नहीं, बल्कि रेफरेंस की तुलना करता है।

मैं एक सिंगल-पास पोस्टऑर्डर DFS का उपयोग करता हूँ। सब-ट्री के लिए, फ़ंक्शन null, खोजा गया एक टारगेट, या पहले से मिला LCA लौटाता है। एक नल नोड null लौटाता है, और किसी भी टारगेट के बराबर वर्तमान नोड स्वयं को लौटाता है। दोनों चिल्ड्रेन में रिकर्स करने के बाद, दो नॉन-नल परिणामों का अर्थ है कि टारगेट पहले वर्तमान नोड पर मिलते हैं, इसलिए मैं इसे लौटाता हूँ। केवल एक नॉन-नल पक्ष के साथ, मैं उस परिणाम को आगे बढ़ाता हूँ।

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

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

सामान्य गलतियाँ

• ट्री को BST मानना और वैल्यू के आधार पर साइड चुनना → आर्बिट्रेरी बाइनरी ट्री में कोई की-ऑर्डरिंग नहीं होती है, और डुप्लिकेट वैल्यू नोड्स की पहचान नहीं करते हैं → संरचना खोजें और नोड रेफरेंस की तुलना करें।
• किसी भी चाइल्ड के नॉन-नल होने पर वर्तमान नोड को लौटाना → एक तरफ का एक टारगेट रूट तक प्रमोट हो जाता है → वर्तमान नोड को केवल तभी लौटाएं जब दोनों पक्ष नॉन-नल हों; अन्यथा नॉन-नल परिणाम को आगे बढ़ाएं।
• यह मान लेना कि p को उत्तर के पूरी तरह नीचे होना चाहिए → एक नोड स्वयं का एन्सेस्टर होता है, इसलिए p उत्तर हो सकता है → वर्तमान नोड पहचान को एक बेस केस बनाएं।
• टारगेट अनुपस्थित होने पर बेस एल्गोरिदम का पुन: उपयोग करना → एक टारगेट खोजने पर भी एक नॉन-नल परिणाम मिलता है → एक मैच काउंट लौटाएं और दोनों को खोजने के बाद ही सफल हों।
• O(1) सहायक स्थान का दावा करना → रिकर्सिव फ्रेम ट्री की ऊँचाई के साथ बढ़ते हैं और एक श्रृंखला पर O(n) तक पहुँचते हैं → O(h) रिपोर्ट करें और गहराई असीमित होने पर एक स्पष्ट स्टैक का उपयोग करें।
• एक क्वेरी के लिए बाइनरी लिफ्टिंग की प्रीकंप्यूटिंग करना → कोड और O(n log n) स्टोरेज एमॉर्टाइज़ नहीं होते हैं → एक क्वेरी के लिए एक DFS का उपयोग करें और केवल कई क्वेरी के लिए प्रीप्रोसेस करें।
• केवल विपरीत पक्षों पर दो लीफ नोड्स का परीक्षण करना → एन्सेस्टर, डुप्लिकेट-वैल्यू, अनुपस्थित-टारगेट और गहराई से संबंधित बग छिपे रहते हैं → अनुबंध सीमाओं के आसपास परीक्षण व्यवस्थित करें।

फॉलो-अप प्रश्न

क्या होगा यदि p या q ट्री में न हों?

रिकर्सन से एक उम्मीदवार नोड और एक मैच काउंट दोनों लौटाएं। अलग-अलग टारगेट के साथ, गिनती 0, 1, या 2 होती है। उम्मीदवार LCA केवल तभी लौटाएं जब रूट परिणाम की गिनती 2 हो; अन्यथा null लौटाएं। बेस एल्गोरिदम को चलाना और केवल नॉन-नल परिणाम की जांच करना अपर्याप्त है क्योंकि उपस्थित एकमात्र टारगेट स्वयं नॉन-नल होता है।

क्या होगा यदि ट्री में 100,000 नोड्स हों और यह पूरी तरह से स्क्यूड हो?

पेरेंट मैप बनाने के लिए एक स्पष्ट स्टैक का उपयोग करें। दोनों टारगेट मिलने के बाद, p के एन्सेस्टर्स को एक सेट में स्टोर करें और पहले प्रतिच्छेदन तक q की पेरेंट श्रृंखला का अनुसरण करें। इसमें O(n) समय और O(n) हीप स्पेस लगता है लेकिन यह 100,000 लैंग्वेज कॉल फ्रेम का उपभोग नहीं करता है। यदि हीप स्पेस भी सीमित है, तो यह मानने के बजाय कि रिकर्सन सुरक्षित है, स्पष्ट करें कि क्या पेरेंट पॉइंटर्स या नियंत्रित ट्रैवर्सल इंटरफ़ेस उपलब्ध हैं।

क्या होगा यदि उसी स्टैटिक ट्री को दस लाख LCA क्वेरी का उत्तर देना हो?

प्रति क्वेरी O(n) DFS अब उपयुक्त नहीं है। O(n log n) समय और स्थान में प्रत्येक नोड की गहराई और उसके 2^k एन्सेस्टर्स की प्रीकंप्यूटिंग करें। प्रत्येक क्वेरी के लिए, गहरे नोड को समान गहराई तक उठाएं, फिर दोनों को सबसे बड़े k से नीचे की ओर उठाएं, जिससे प्रति क्वेरी O(log n) समय मिलता है। और भी बड़ी क्वेरी मात्राओं पर, यूलर टूर प्लस RMQ का मूल्यांकन किया जा सकता है; अपडेट फ्रीक्वेंसी, मेमोरी और लेटेंसी आवश्यकताएं तय करती हैं कि कौन सी प्रीप्रोसेसिंग योजना उपयुक्त है।

क्या होगा यदि प्रत्येक नोड में पहले से ही एक पेरेंट पॉइंटर हो?

रूट से ट्रैवर्स करने की कोई आवश्यकता नहीं है। दोनों गहराइयों की गणना करें, गहरे नोड को तब तक ऊपर उठाएं जब तक कि गहराई मेल न खाए, फिर दोनों को तब तक ऊपर ले जाएं जब तक कि वे बराबर न हो जाएं। इसमें O(h) समय और O(1) अतिरिक्त स्थान लगता है। वैकल्पिक रूप से, p के सभी एन्सेस्टर्स को स्टोर करें और q से ऊपर चलें; वह सरल है लेकिन O(h) सेट का उपयोग करता है।

बाइनरी सर्च ट्री के लिए समाधान कैसे बदलता है?

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