ধরা যাক একটি বাইনারি ট্রি আছে, এটি একটি বৈধ বাইনারি সার্চ ট্রি (BST) কিনা তা চেক করতে হবে। একটি BST এর ডেফিনিশন নিচের মতো:
- এক নোডের লেফট সাবট্রিতে শুধু সেই নোডের কী থেকে ছোট কী-वाले নোড থাকবে।
- এক নোডের রাইট সাবট্রিতে শুধু সেই নোডের কী থেকে বড় কী-वाले নোড থাকবে।
- লেফট এবং রাইট সাবট্রি দুটোই বাইনারি সার্চ ট্রি হতে হবে।
তাই যদি ট্রি হয়:
আউটপুট হবে true।
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:
- solve() নামে একটি রিকারসিভ ফাংশন তৈরি করুন, এটি root, min এবং max নেবে। মেথডটি হবে এইভাবে:
- যদি root null হয়, তবে true রিটার্ন করুন
- যদি root-এর মান <= min বা root-এর মান >= max হয়, তবে false রিটার্ন করুন
- (solve(রুটের লেফট, min, রুটের মান) AND solve(রুটের রাইট, রুটের মান, max)) রিটার্ন করুন
- প্রাথমিকভাবে solve() মেথড কল করুন, root, -inf as min এবং inf as max পাস করে।
উদাহরণ (পাইথন):
নিচের ইমপ্লিমেন্টেশনটি দেখে আরও ভালো বুঝতে পারবেন:
class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right def insert(temp,data): que = [] que.append(temp) while (len(que)): temp = que[0] que.pop(0) if (not temp.left): if data is not None: temp.left = TreeNode(data) else: temp.left = TreeNode(0) break else: que.append(temp.left) if (not temp.right): if data is not None: temp.right = TreeNode(data) else: temp.right = TreeNode(0) break else: que.append(temp.right) def make_tree(elements): Tree = TreeNode(elements[0]) for element in elements[1:]: insert(Tree, element) return Tree class Solution(object): def isValidBST(self, root): return self.solve(root,-1000000000000000000000,1000000000000000000000) def solve(self,root,min_val,max_val): if root == None or root.data == 0: return True if (root.data <= min_val or root.data >=max_val): return False return self.solve(root.left,min_val,root.data) and self.solve(root.right,root.data,max_val) ob1 = Solution() tree = make_tree([3,1,4,None,2,None,5]) print(ob1.isValidBST(tree)) tree = make_tree([5,1,4,None,None,3,6]) print(ob1.isValidBST(tree))
ইনপুট
[3,1,4,null,2,null,5] [5,1,4,null,null,3,6]
আউটপুট
true false
