पायथन में BST में रेंज में नोड्स की संख्या खोजने का प्रोग्राम

मान लीजिए हमारे पास एक BST है, और हमारे पास बाएं और दाएं बाउंड l और r भी हैं, हमें रूट में उन सभी नोड्स की संख्या गिननी है जिनके मान l और r के बीच हैं (सम्मिलित)।

उदाहरण के लिए, यदि इनपुट जैसा है: l = 7, r = 13, तो आउटपुट 3 होगा, क्योंकि तीन नोड्स हैं: 8, 10, 12।

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

• stack := एक स्टैक और पहले रूट डालें, count := 0
• जब तक स्टैक खाली नहीं है, करें:
  • node := स्टैक का शीर्ष तत्व, और पॉप करें
  • यदि node null नहीं है, तो:
    • यदि l <= node का डेटा <= r, तो:
      • count := count + 1
      • स्टैक में node का दायां और बायां डालें
    • अन्यथा यदि node का डेटा < l, तो स्टैक में node का दायां डालें
    • अन्यथा, स्टैक में node का बायां डालें
• count वापस करें

उदाहरण

from collections import deque
class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class Solution:
    def solve(self, root, l, r):
        stack, count = [root], 0
        while stack:
            node = stack.pop()
            if node:
                if l <= node.data <= r:
                    count += 1
                    stack += [node.right, node.left]
                elif node.data < l:
                    stack += [node.right]
                else:
                    stack += [node.left]
        return count

ob = Solution()
root = TreeNode(12)
root.left = TreeNode(8)
root.right = TreeNode(15)
root.left.left = TreeNode(3)
root.left.right = TreeNode(10)
print(ob.solve(root, 7, 13))

इनपुट

root = TreeNode(12) root.left = TreeNode(8) root.right = TreeNode(15) root.left.left = TreeNode(3) root.left.right = TreeNode(10) 7,13

आउटपुट

3