পাইথনে একটি বাইনারি সার্চ ট্রিতে kth ক্ষুদ্রতম উপাদান খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি বাইনারি সার্চ ট্রি আছে, এবং আরেকটি পূর্ণসংখ্যা k আছে আমাদের গাছের kth ক্ষুদ্রতম মান খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুট মত হয়

k =3, তাহলে আউটপুট হবে 7

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• স্ট্যাক :=একটি খালি স্ট্যাক

• i :=0

• উত্তর :=-1

• স্ট্যাক খালি না হলে বা রুট শূন্য না হলে, করুন

  • রুট শূন্য না হলে, করুন

    • স্ট্যাকের মধ্যে রুট পুশ করুন

    • root :=রুটের বাম

  • v :=স্ট্যাক থেকে পপ উপাদান

  • যদি আমি k এর মত হয়, তাহলে

    • উত্তর :=v এর মান

    • লুপ থেকে বেরিয়ে আসুন

  • root :=v

    এর ডানদিকে

  • i :=i + 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