মনে করুন একটি বাইনারি ট্রি আছে। এটি বাইনারি সার্চ ট্রি (BST) কিনা যাচাই করতে হবে। BST-এর বৈশিষ্ট্য:
- বাম সাবট্রির সব নোড বর্তমান নোড চেয়ে ছোট।
- ডান সাবট্রির সব নোড বর্তমান নোড চেয়ে বড়।
- এই বৈশিষ্ট্য রিকার্সিভলি সব নোডের জন্য সত্য।
ইনপুট ট্রির ছবি দেওয়া আছে, আউটপুট True।
সমাধানের ধাপসমূহ
- x := ট্রির ইনঅর্ডার ট্রাভার্সাল সিকোয়েন্স
- যদি x সর্টেড হয়, True ফেরত দিন
- অন্যথায় False ফেরত দিন
উদাহরণ
class TreeNode:
def __init__(self, data, left = None, right = None):
self.data = data
self.left = left
self.right = right
class Solution:
def solve(self, root):
def inorder(root,l):
if root is None:
return
inorder(root.left,l)
l.append(root.data)
inorder(root.right,l)
l = []
inorder(root,l)
return l == sorted(l)
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(1)
root.right = TreeNode(9)
root.right.left = TreeNode(7)
root.right.right = TreeNode(10)
root.right.left.left = TreeNode(6)
root.right.left.right = TreeNode(8)
print(ob.solve(root))ইনপুট
root = TreeNode(5) root.left = TreeNode(1) root.right = TreeNode(9) root.right.left = TreeNode(7) root.right.right = TreeNode(10) root.right.left.left = TreeNode(6) root.right.left.right = TreeNode(8)
আউটপুট
True
