পাইথনে বাইনারি ট্রি থেকে সর্বোচ্চ BST সাবট্রি খুঁজে বের করার প্রোগ্রাম

একটি বাইনারি ট্রি দেওয়া আছে। ট্রির মধ্যে এমন একটি সাবট্রি খুঁজে বের করতে হবে যা বাইনারি সার্চ ট্রি (BST) এবং নোড সংখ্যা সর্বোচ্চ।

উদাহরণস্বরূপ, নিচের ট্রির জন্য বড় BST সাবট্রি হলো 4, 5, 6 (রুট ৫) → আউটপুট: 4, 5, 6,।

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

সমাধানের পদ্ধতি (পোস্ট-অর্ডার ট্রাভার্সাল + সর্টেড চেক)

1. max_size = [0], max_node = [None]।
2. traverse(node) ফাংশন ডিফাইন করুন যা ইনঅর্ডার ট্রাভার্সাল রিটার্ন করে (বাম + রুট + ডান)।
   • যদি রিটার্ন করা লিস্ট সর্টেড হয়, তবে এটি একটি BST। আকার বড় হলে max_size এবং max_node আপডেট করুন।
3. traverse(root) কল করুন।
4. max_node[0] রিটার্ন করুন।

দ্রষ্টব্য: এই পদ্ধতিটি O(n²) সময় নেয় (প্রতিটি নোডে সর্টেড চেক)। অপ্টিমাইজড O(n) সমাধানের জন্য নোডের মিন/ম্যাক্স ভ্যালু ও BST প্রোপার্টি ট্র্যাক করতে হয়।

পাইথন কোড উদাহরণ

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:
        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) ... (উপরের ট্রি)

আউটপুট

4, 5, 6,