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

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

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

उदाहरण के लिए, यदि इनपुट जैसा है: तो आउटपुट True होगा।

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

• 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