पायथन में दिए गए पेड़ से सबसे बड़ा बाइनरी सर्च सबट्री खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमें बाइनरी सर्च ट्री के रूप में सबसे बड़ा सबट्री (अधिकतम संख्या में नोड्स के साथ) खोजना होगा।

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

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

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

• अधिकतम_आकार:=[0]
• max_node :=[null]
• एक फ़ंक्शन ट्रैवर्स () को परिभाषित करें। यह नोड लेगा
• यदि नोड शून्य है, तो
  • वापसी शून्य
• बाएं:=ट्रैवर्स(नोड के बाएं)
• दाएं:=ट्रैवर्स (नोड के दाएं)
• पहली:=बाएँ + [नोड का मान] + दाएँ
• अगर lst को सॉर्ट किया जाता है, तो
  • यदि max_size[0]
  • max_size[0] :=lst का आकार
  • max_node[0] :=नोड

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

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

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.val = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.val, end = ', ')
      print_tree(root.right)
class Solution:
   def solve(self, root):
      max_size = [0]
      max_node = [None]
      def traverse(node):
         if not node:
            return []
      left = traverse(node.left)
      right = traverse(node.right)
      lst = left + [node.val] + right
      if sorted(lst) == lst:
         if max_size[0] < len(lst):
            max_size[0] = len(lst)
            max_node[0] = node
      return lst

   traverse(root)
   return max_node[0]
ob = Solution()
root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)
print_tree(ob.solve(root))

इनपुट

root = TreeNode(12)
root.left = TreeNode(3)
root.right = TreeNode(5)
root.right.left = TreeNode(4)
root.right.right = TreeNode(6)

आउटपुट

4, 5, 6,