পাইথনে বাইনারি ট্রি-তে BST আছে কিনা যাচাই করার প্রোগ্রাম

একটি বাইনারি ট্রি দেওয়া আছে। ট্রি-টির থেকে সবচেয়ে বড় সাবট্রি বের করতে হবে যা একটি বাইনারি সার্চ ট্রি (BST)। BST-এর রুট নোড রিটার্ন করতে হবে।

ইনপুট ট্রি:

আউটপুট:

সমাধানের ধাপসমূহ

• c := 0, m := null
• recurse() ফাংশন সংজ্ঞায়িত করুন। এটি node গ্রহণ করবে:
  • যদি node null নয় হয়:
    • left_val := recurse(node.left)
    • right_val := recurse(node.right)
    • count := negative infinity
    • যদি (node.left == null বা node.left.val <= node.val) এবং (node.right == null বা node.val <= node.right.val) হয়:
      • count := left_val + right_val + 1
    • যদি count > c হয়:
      • c := count, m := node
    • count ফেরত দিন
  • 0 ফেরত দিন
• recurse(root)
• m ফেরত দিন

উদাহরণ

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,