একটি বাইনারি গাছে, প্রতিটি নোডে দুটি শিশু থাকে, যেমন বাম শিশু এবং ডান শিশু। ধরা যাক আমাদের একটি বাইনারি গাছ আছে এবং আমাদের পরীক্ষা করতে হবে গাছটি সুষম কিনা। একটি বাইনারি গাছকে ভারসাম্য বলা হয় যদি বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য '1' এর কম বা সমান হয়।
উদাহরণ
ইনপুট-1:
আউটপুট:
True
ব্যাখ্যা:
প্রদত্ত বাইনারি ট্রি হল [1,2,3, NULL, NULL, 6, 7]। এর বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য '1' এর সমান, এইভাবে এটি একটি উচ্চতা ভারসাম্যপূর্ণ গাছ।
ইনপুট-2:
আউটপুট:
False
ব্যাখ্যা:
প্রদত্ত বাইনারি ট্রি হল [1,2,3,4, NULL, NULL,NULL,5]। এর বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য '1' এর চেয়ে বেশি, তাই এটি একটি উচ্চতা ভারসাম্যপূর্ণ গাছ নয়।
এই সমস্যা সমাধানের পদ্ধতি
এই সমস্যাটি সমাধান করার জন্য পুনরাবৃত্তিমূলক পদ্ধতি হল বাম সাবট্রি এবং ডান সাবট্রির উচ্চতা খুঁজে বের করা এবং তারপর পরীক্ষা করা যদি (উচ্চতা(বাম গাছ) - উচ্চতা(রাইটসাবট্রি) <=1) এবং সেই অনুযায়ী সত্য বা মিথ্যা ফেরত দেয়। তারপর, আমরা বাইনারি গাছের প্রতিটি নোডের জন্য বারবার পরীক্ষা করব।
- একটি বাইনারি ট্রির নোডের ইনপুট নিন।
- গাছের উচ্চতা বের করার জন্য একটি ফাংশন সংজ্ঞায়িত করুন।
- বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য '1'-এর বেশি না হলে বারবার চেক করার জন্য একটি বুলিয়ান ফাংশন, তারপর ট্রু রিটার্ন করুন।
- ফলাফল ফেরত দিন।
উদাহরণ
class treenode:
def __init__(self, data):
self.data = data
self.left = self.right = None
# funtion to find the height of the left subtree and right subtree
class height:
def __init__(self):
self.height = 0
# function to check if the tree is balanced or not
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]। এর বাম সাবট্রি এবং ডান সাবট্রির উচ্চতার পার্থক্য '1' এর সমান, এইভাবে এটি একটি উচ্চতা ভারসাম্যপূর্ণ গাছ।
