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

मान लीजिए हमें एक बाइनरी ट्री दी गई है। हमें ट्री से सबसे बड़ा सबट्री ढूंढना है जो बाइनरी सर्च ट्री (BST) है। हम BST का रूट नोड लौटाते हैं।

इसलिए, यदि इनपुट है:

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

समाधान दृष्टिकोण

• पोस्ट-ऑर्डर ट्रैवर्सल का उपयोग करके प्रत्येक सबट्री की जांच करें
• ट्रैक करें कि सबट्री BST है या नहीं
• सबसे बड़े BST का रूट नोड लौटाएं

उदाहरण कार्यान्वयन

class TreeNode:
    def __init__(self, val, left=None, right=None):
        self.val = val
        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

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.val, end=', ')
        print_tree(root.right)

def solve(root):
    c, m = 0, None
    
    def recurse(node):
        nonlocal c, m
        if node:
            left_val = recurse(node.left)
            right_val = recurse(node.right)
            count = -float("inf")
            if (node.left is None or node.left.val <= node.val) and (node.right is None or node.val <= node.right.val):
                count = left_val + right_val + 1
            if count > c:
                c = count
                m = node
            return count
        return 0
    
    recurse(root)
    return m

tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))

इनपुट

tree = make_tree([1, 4, 6, 3, 5])
print_tree(solve(tree))

आउटपुट

3, 4, 5,