পাইথনে BST-এ Kth Smallest Element (K-তম ক্ষুদ্রতম উপাদান)

মান করুন একটি বাইনারি সার্চ ট্রি (BST) আছে। আমাদের সেটিতে K-তম ক্ষুদ্রতম উপাদান বের করতে হবে। ট্রি যদি নিচের মতো হয়:

যদি আমরা ৩-রা ক্ষুদ্রতম উপাদান খুঁজি (k = 3), তবে ফলাফল হবে ৭।

সমাধানের ধাপগুলো (ইন-অর্ডার ট্রাভার্সাল):

• একটি খালি লিস্ট nodes তৈরি করুন
• solve(root, nodes) কল করুন
• nodes[k-1] রিটার্ন করুন
• solve মেথডটি নিচের মতো কাজ করবে:
  • যদি রুট নাল হয়, তবে রিটার্ন করুন
  • solve(root.left, nodes)
  • root.data nodes অ্যারেতে যোগ করুন
  • solve(root.right, nodes)

নিচে ইমপ্লিমেন্টেশন দেওয়া হলো:

উদাহরণ

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 is 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