পাইথনে একটি বাইনারি ট্রিতে সবচেয়ে বড় কমপ্লিট সাবট্রি খুঁজুন

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া আছে। এতে সর্বাধিক আকারের কমপ্লিট সাব-ট্রির আকার বের করতে হবে। কমপ্লিট বাইনারি ট্রি বলতে হয় সকল লেভেল সম্পূর্ণ ভরা থাকে, শুধু শেষ লেভেল হয়তো আংশিকভাবে ভরা থাকে এবং সেটাও যতটা সম্ভব বামদিকেই থাকে।

উদাহরণস্বরূপ, ইনপুট ট্রি নিচের চিত্রের মতো হলে আউটপুট হবে আকার ৪ এবং ইনঅর্ডার ট্রাভার্সাল হবে 10, 45, 60, 70।

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

1. একটি রিটার্ন টাইপ সংজ্ঞায়িত করুন যার ফিল্ডগুলো: isComplete, isPerfect (প্রাথমিকভাবে False), size (প্রাথমিকভাবে ০), rootTree (প্রাথমিকভাবে None)।
2. checkCompleteness(root) ফাংশন লিখুন:
   • যদি root নাল হয়, তবে isPerfect=True, isComplete=True, size=0, rootTree=None রিটার্ন করুন।
   • বাম এবং ডান সাবট্রির জন্য রিকার্সিভলি checkCompleteness কল করুন।
   • যদি বাম সাবট্রি পারফেক্ট হয়, ডান সাবট্রি কমপ্লিট হয় এবং উভয়ের উচ্চতা সমান হয়, তবে বর্তমান নোডও কমপ্লিট। সাইজ আপডেট করুন এবং রিটার্ন করুন।
   • যদি বাম সাবট্রি কমপ্লিট হয়, ডান সাবট্রি পারফেক্ট হয় এবং বামের উচ্চতা ডানের চেয়ে ১ বেশি হয়, তবে বর্তমান নোডও কমপ্লিট। সাইজ আপডেট করুন এবং রিটার্ন করুন।
   • অন্যথায় বর্তমান নোড কমপ্লিট নয়। সাইজ হবে বাম ও ডান সাবট্রির সর্বোচ্চ সাইজ। বড় সাইজের সাবট্রির রুট rootTree হিসেবে সেট করুন।

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

import math

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

class ReturnType:
    def __init__(self):
        self.isPerfect = None
        self.isComplete = None
        self.size = 0
        self.rootTree = None

def getHeight(size):
    return int(math.ceil(math.log(size + 1) / math.log(2)))

def checkCompleteness(root):
    ret = ReturnType()
    if root is None:
        ret.isPerfect = True
        ret.isComplete = True
        ret.size = 0
        ret.rootTree = None
        return ret
    left_tree = checkCompleteness(root.left)
    right_tree = checkCompleteness(root.right)
    if (left_tree.isPerfect and right_tree.isComplete and
        getHeight(left_tree.size) == getHeight(right_tree.size)):
        ret.isComplete = True
        ret.isPerfect = right_tree.isPerfect
        ret.size = left_tree.size + right_tree.size + 1
        ret.rootTree = root
        return ret
    if (left_tree.isComplete and right_tree.isPerfect and
        getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
        ret.isComplete = True
        ret.isPerfect = False
        ret.size = left_tree.size + right_tree.size + 1
        ret.rootTree = root
        return ret
    ret.isPerfect = False
    ret.isComplete = False
    ret.size = max(left_tree.size, right_tree.size)
    if left_tree.size > right_tree.size:
        ret.rootTree = left_tree.rootTree
    else:
        ret.rootTree = right_tree.rootTree
    return ret

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

# ট্রি তৈরি
root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

ans = checkCompleteness(root)
print("Size:", ans.size)
print("Inorder Traversal: ", end='')
print_tree(ans.rootTree)

ইনপুট

root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

আউটপুট

Size: 4
Inorder Traversal: 10, 45, 60, 70,