পাইথনে বাইনারি ট্রি-র সর্বোচ্চ পারফেক্ট সাবট্রির আকার নির্ণয়

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

উদাহরণ

ইনপুট ট্রি: 2 / \ 3 4 / \ / 5 6 7

আউটপুট: আকার = ৩, সাবট্রি রুট = ৩ (নোড ৫, ৩, ৬)

সমাধানের পদ্ধতি

1. পোস্ট-অর্ডার ট্রাভার্সাল (Post-order traversal) ব্যবহার করা হয়।
2. প্রতিটি নোডের জন্য রিটার্ন করা হয়: (isPerfect, height, rootTree)
3. বেস কেস: NULL নোড → (True, 0, None)
4. বাম ও ডান সাবট্রি রিকার্সিভলি চেক করা হয়।
5. যদি দুটি সাবট্রি পারফেক্ট হয় এবং উঁচুই সমান হয়, তবে বর্তমান নোডও পারফেক্ট।
6. অন্যথায়, বাম ও ডান সাবট্রির মধ্যে বড়টিই সর্বোচ্চ পারফেক্ট সাবট্রি।

পাইথন কোড

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class RetType:
    def __init__(self):
        self.isPerfect = False
        self.height = 0
        self.rootTree = None

def get_perfect_subtree(root):
    r_type = RetType()
    if root is None:
        r_type.isPerfect = True
        r_type.height = 0
        r_type.rootTree = None
        return r_type
    
    left_subtree = get_perfect_subtree(root.left)
    right_subtree = get_perfect_subtree(root.right)
    
    if (left_subtree.isPerfect and right_subtree.isPerfect and 
        left_subtree.height == right_subtree.height):
        r_type.height = left_subtree.height + 1
        r_type.isPerfect = True
        r_type.rootTree = root
        return r_type
    
    r_type.isPerfect = False
    r_type.height = max(left_subtree.height, right_subtree.height)
    if left_subtree.height > right_subtree.height:
        r_type.rootTree = left_subtree.rootTree
    else:
        r_type.rootTree = right_subtree.rootTree
    return r_type

# Example usage
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.left.left = TreeNode(5)
root.left.right = TreeNode(6)
root.right.left = TreeNode(7)

res = get_perfect_subtree(root)
h = res.height
print("Size:", 2**h - 1)
print("Tree nodes:", end=" ")
# Inorder traversal to print
def print_tree(node):
    if node:
        print_tree(node.left)
        print(node.data, end=", ")
        print_tree(node.right)
print_tree(res.rootTree)

ইনপুট

ট্রি গঠন: root=2, left=3, right=4, left.left=5, left.right=6, right.left=7

আউটপুট

Size: 3 Tree: 5, 3, 6,