पायथन में एक BST में Kth सबसे छोटा तत्व

मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है। हमें उस BST में Kth सबसे छोटा तत्व खोजना है। तो अगर पेड़ जैसा है -

तो अगर हम तीसरा सबसे छोटा तत्व खोजना चाहते हैं, तो 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