पायथन में बाइनरी ट्री BST है या नहीं, यह जांचने के लिए प्रोग्राम

मान लीजिए हमारे पास बाइनरी ट्री है; हमें यह जांचना होगा कि यह बाइनरी सर्च ट्री है या नहीं। जैसा कि हम जानते हैं कि बीएसटी में निम्नलिखित गुण होते हैं -

• इसके बाएँ उपप्रकार के सभी नोड वर्तमान नोड मान से छोटे हैं
• इसके दाहिने सबट्री के सभी नोड वर्तमान नोड मान से बड़े हैं
• ये गुण सभी नोड्स के लिए पुनरावर्ती रूप से धारण करते हैं

तो, अगर इनपुट पसंद है

तो आउटपुट सही होगा

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

• x :=वृक्ष तत्वों के क्रमागत ट्रैवर्सल अनुक्रम की सूची
• अगर x को सॉर्ट किया जाता है, तो
  • सही लौटें
• झूठी वापसी

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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):
      def inorder(root,l):
         if root is None:
            return
            inorder(root.left,l) l.append(root.data)
            inorder(root.right,l)
            l = []
            inorder(root,l)
         return l == sorted(l)
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8) print(ob.solve(root))

इनपुट

root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)

आउटपुट

True