একটি বাইনারি ট্রিতে প্রতিটি নোডের দুটি চাইল্ড থাকে—বাম চাইল্ড এবং ডান চাইল্ড। ধরি আমাদের একটি বাইনারি ট্রি আছে এবং আমাদের চেক করতে হবে যে ট্রিটি সুসঙ্গত (balanced) কিনা। একটি বাইনারি ট্রিকে সুসঙ্গত বলা হয় যদি এর বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য ১-এর চেয়ে কম বা সমান হয়।
উদাহরণ
ইনপুট-১:
আউটপুট:
True
ব্যাখ্যা:
দেওয়া বাইনারি ট্রিটি হলো [1,2,3, NULL, NULL, 6, 7]। এর বাম ও ডান সাবট্রির উচ্চতার পার্থক্য ১, তাই এটি একটি উচ্চতা-সুসঙ্গত ট্রি।
ইনপুট-২:
আউটপুট:
False
ব্যাখ্যা:
দেওয়া বাইনারি ট্রিটি হলো [1,2,3,4, NULL, NULL, NULL, 5]। এর বাম ও ডান সাবট্রির উচ্চতার পার্থক্য ১-এর চেয়ে বেশি, তাই এটি একটি উচ্চতা-সুসঙ্গত ট্রি নয়।
সমস্যা সমাধানের পদ্ধতি
এই সমস্যা সমাধানের জন্য রিকার্সিভ পদ্ধতিতে বাম ও ডান সাবট্রির উচ্চতা বের করে পরীক্ষা করা হয় যে পার্থক্য ১-এর চেয়ে কম বা সমান কিনা। তারপর ট্রির প্রতিটি নোডের জন্য একই কাজ রিকার্সিভভাবে दुहरানো হয়।
- বাইনারি ট্রির নোডগুলো ইনপুট olarak নিন।
- ট্রির উচ্চতা বের করার জন্য একটি ফাংশন সংজ্ঞায়িত করুন।
- একটি বুলিয়ান ফাংশন লিখুন যা রিকার্সিভভাবে যাচাই করবে বাম ও ডান সাবট্রির উচ্চতার পার্থক্য ১-এর চেয়ে বেশি নয় কিনা।
- ফলাফল রিটার্ন করুন।
পাইথন কোড উদাহরণ
class TreeNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# ট্রির উচ্চতা বের করার ক্লাস
class Height:
def __init__(self):
self.height = 0
# ট্রি সুসঙ্গত কিনা যাচাই করার ফাংশন
def isBalanced(root):
lh = Height()
rh = Height()
if root is None:
return True
return (abs(lh.height - rh.height) <= 1) and isBalanced(root.left) and isBalanced(root.right)
# ট্রি তৈরি
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = None
root.left.right = None
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
if isBalanced(root):
print("সুসঙ্গত (Balanced)")
else:
print("অসুসঙ্গত (Not Balanced)")
আউটপুট
সুসঙ্গত (Balanced)
দেওয়া বাইনারি ট্রি [1, 2, 3, NULL, NULL, 6, 7]। এর বাম ও ডান সাবট্রির উচ্চতার পার্থক্য ১, তাই এটি একটি উচ্চতা-সুসঙ্গত ট্রি।
