পাইথনে একটি বাইনারি ট্রি রেড-ব্ল্যাক ট্রির মতো উচ্চতা-সামঞ্জস্যপূর্ণ কিনা তা যাচাই করুন

সমস্যা বিবরণ

একটি রেড-ব্ল্যাক ট্রিতে, কোনো নোডের সর্বোচ্চ উচ্চতা তার ন্যূনতম উচ্চতার চেয়ে højপথ দ্বিগুণ হতে পারে। একটি বাইনারি সার্চ ট্রি দেওয়া থাকলে, প্রতিটি নোডের জন্য নোড থেকে পাতা পর্যন্ত সবচেয়ে দীর্ঘ পথের দৈর্ঘ্য, নোড থেকে পাতা পর্যন্ত সবচেয়ে ছোট পথের নোড সংখ্যার দ্বিগুণের চেয়ে বেশি হবে না। এই বৈশিষ্ট্য যাচাই করতে হবে।

উদাহরণস্বরূপ, ইনপুট ট্রি নিচের চিত্রের মতো হলে আউটপুট হবে True, কারণ এটি সামঞ্জস্যপূর্ণ।

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

1. solve() ফাংশন সংজ্ঞায়িত করুন যা root, max_height, min_height আর্গুমেন্ট হিসেবে নেয়।
2. যদি root নাল হয়, তবে max_height এবং min_height ০ সেট করুন এবং True রিটার্ন করুন।
3. বাম এবং ডান সাবট্রির জন্য left_max, left_min, right_max, right_min ভেরিয়েবল শুরু করুন।
4. বাম সাবট্রির জন্য solve() কল করুন। যদি এটি False রিটার্ন করে, তবে False রিটার্ন করুন।
5. ডান সাবট্রির জন্য একইভাবে solve() কল করুন।
6. বর্তমান নোডের max_height = max(left_max, right_max) + 1 এবং min_height = min(left_min, right_min) + 1 হিসাব করুন।
7. যদি max_height <= 2 * min_height হয়, তবে True রিটার্ন করুন, অন্যথায় False।
8. মূল পদ্ধতিতে max_height এবং min_height ০ দিয়ে শুরু করে solve(root, max_height, min_height) কল করুন।

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

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

def solve(root, max_height, min_height):
    if root is None:
        max_height = min_height = 0
        return True
    left_max = left_min = 0
    right_max = right_min = 0
    if solve(root.left, left_max, left_min) == False:
        return False
    if solve(root.right, right_max, right_min) == False:
        return False
    max_height = max(left_max, right_max) + 1
    min_height = min(left_min, right_min) + 1
    if max_height <= 2 * min_height:
        return True
    return False

def is_tree_balanced(root):
    max_height, min_height = 0, 0
    return solve(root, max_height, min_height)

# ট্রি তৈরি
root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)

print(is_tree_balanced(root))  # আউটপুট: True

ইনপুট

root = TreeNode(10)
root.left = TreeNode(5)
root.right = TreeNode(100)
root.right.left = TreeNode(50)
root.right.right = TreeNode(150)
root.right.left.left = TreeNode(40)

আউটপুট

True