पायथन में बाइनरी सर्च ट्री को मान्य करें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, यह जांचने के लिए निर्धारित करें कि यह एक वैध बाइनरी सर्च ट्री (BST) है या नहीं। मान लें कि एक बीएसटी को इस प्रकार परिभाषित किया गया है -

• नोड का बायां सबट्री नोड की कुंजी से छोटी कुंजियों वाली केवल नोड रखता है।
• नोड का दायां सबट्री नोड की कुंजी से बड़ी कुंजियों वाले केवल नोड रखता है।
• बाएं और दाएं दोनों उपवृक्ष भी द्विआधारी खोज वृक्ष होने चाहिए।

तो अगर पेड़ ऐसा है -

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

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

• एक पुनरावर्ती फ़ंक्शन बनाएं जिसे हल () कहा जाता है, यह रूट, न्यूनतम और अधिकतम लेगा, विधि इस तरह होगी
• अगर रूट शून्य है, तो सही लौटें
• यदि रूट का मान <=न्यूनतम या रूट का मान>=अधिकतम, तो गलत लौटाएं
• रिटर्न (समाधान (रूट के बाएं, न्यूनतम, मूल मान) और हल करें (रूट का अधिकार, मूल मान, अधिकतम))
• रूट को पास करके हल () विधि को प्रारंभ में कॉल करें, और - inf को min और inf को अधिकतम करें।

उदाहरण (पायथन)

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

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):
         if data is not None:
            temp.left = TreeNode(data)
         else:
            temp.left = TreeNode(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if data is not None:
            temp.right = TreeNode(data)
         else:
            temp.right = TreeNode(0)
         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 isValidBST(self, root):
      return self.solve(root,-1000000000000000000000,1000000000000000000000)
   def solve(self,root,min_val,max_val):
      if root == None or root.data == 0:
         return True
      if (root.data <= min_val or root.data >=max_val):
         return False
      return self.solve(root.left,min_val,root.data) and self.solve(root.right,root.data,max_val)
ob1 = Solution()
tree = make_tree([3,1,4,None,2,None,5])
print(ob1.isValidBST(tree))
tree = make_tree([5,1,4,None,None,3,6])
print(ob1.isValidBST(tree))

इनपुट

[3,1,4,null,2,null,5]
[5,1,4,null,null,3,6]

आउटपुट

true
false