मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें उस BST में Kवां सबसे छोटा एलिमेंट ढूंढना है। इसलिए यदि ट्री इस तरह है -
इसलिए यदि हम 3रा सबसे छोटा एलिमेंट ढूंढना चाहते हैं, तो k = 3, और परिणाम 7 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- nodes नामक एक खाली लिस्ट बनाएं
- solve(root, nodes) कॉल करें
- nodes के k - 1वें एलिमेंट को लौटाएं
- solve मेथड बनाया गया है, यह रूट और nodes ऐरे लेता है, यह इस तरह काम करेगा -
- यदि रूट null है, तो लौट जाएं
- solve(रूट का लेफ्ट, nodes)
- रूट की वैल्यू को nodes ऐरे में जोड़ें
- solve(रूट का राइट, nodes)
यह इनऑर्डर ट्रैवर्सल का उपयोग करता है जो BST में एलिमेंट्स को सॉर्टेड क्रम में देता है।
बेहतर समझ के लिए निम्न कार्यान्वयन देखें -
उदाहरण
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
