पायथन में बाइनरी सर्च ट्री में kth सबसे छोटा तत्व खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है, और एक और पूर्णांक k है, तो हमें ट्री में kth सबसे छोटा मान खोजना होगा।

तो, अगर इनपुट पसंद है

k =3, तो आउटपुट 7 होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• स्टैक :=एक खाली स्टैक

• मैं :=0

• उत्तर :=-1

• जबकि स्टैक खाली नहीं है या रूट शून्य नहीं है, करें

  • जबकि रूट शून्य नहीं है, करें

    • जड़ को ढेर में धकेलें

    • जड़ :=जड़ के बाएँ

  • v:=स्टैक से पॉप एलिमेंट

  • अगर मैं k के समान हूं, तो

    • Ans :=v का मान

    • लूप से बाहर आएं

  • जड़ :=वी के दायें

  • मैं :=मैं + 1

• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class TreeNode:
   def __init__(self, value):
      self.val = value
      self.left = None
      self.right = None

class Solution:
   def solve(self, root, k):
      stack = []
      i = 0
      ans = -1
      while stack or root:
         while root:
            stack.append(root)
               root = root.left
         v = stack.pop()
         if i == k:
            ans = v.val
            break
         root = v.right
         i += 1
      return ans
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root, 3))

इनपुट

root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
3

आउटपुट

7