ধরুন আমাদের একটি বাইনারি সার্চ ট্রি আছে। আমাদের সেই BST-তে Kth ক্ষুদ্রতম উপাদান খুঁজে বের করতে হবে। তাই গাছটি যদি −
এর মত হয়
সুতরাং আমরা যদি 3য় ক্ষুদ্রতম উপাদান খুঁজে পেতে চাই, তাহলে k =3 এবং ফলাফল হবে 7।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- নোড নামে একটি খালি তালিকা তৈরি করুন
- কল সল্ভ (রুট, নোড)
- রিটার্ন k – নোডের ১ম উপাদান
- সমাধান পদ্ধতি তৈরি করা হয়েছে, এটি রুট এবং নোড অ্যারে নেয়, এটি নিম্নরূপ কাজ করবে -
- যদি রুট শূন্য হয়, তাহলে ফিরুন
- সমাধান (রুটের বামে, নোড)
- নোড অ্যারেতে রুটের মান যোগ করুন
- সমাধান (রুট, নোডের ডানদিকে)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): temp.left = TreeNode(data) break else: que.append(temp.left) if (not temp.right): temp.right = TreeNode(data) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def kthSmallest(self, root, k): nodes = [] self.solve(root,nodes) return nodes[k-1] def solve(self, root,nodes): if root == None: return self.solve(root.left,nodes) nodes.append(root.data) self.solve(root.right,nodes) ob1 = Solution() tree = make_tree([10,5,15,2,7,13]) print(ob1.kthSmallest(tree, 3))
ইনপুট
[10,5,15,2,7,13] 3
আউটপুট
7
