পাইথনে বাইনারি সার্চ ট্রিতে k-তম সবচেয়ে ছোট উপাদান খুঁজে বের করার প্রোগ্রাম

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

উদাহরণ ট্রি এবং k = 3 হলে আউটপুট 7।

সমাধানের ধাপসমূহ

• stack := খালি স্ট্যাক, i := 0, ans := -1
• যখন stack খালি নয় বা root null নয়:
• যখন root null নয়: stack-এ root পুশ করুন, root := root.left
• v := stack.pop()
• যদি i == k হয়, ans := v.val, ব্রেক করুন।
• root := v.right, i := i + 1
• ans ফেরত দিন।

উদাহরণ কোড

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