একটি ট্রি বাইনারি সার্চ ট্রি হলে এর সব লেফট চাইল্ড নোডের মান থেকে ছোট হবে এবং সব রাইট চাইল্ড নোডের মান থেকে বড় হবে। প্রথমে চেক করি নোডে কোনো মান আছে কিনা, যদি নোড null হয় তবে বৈধ বাইনারি সার্চ ট্রি বলে true রিটার্ন করি। নোড null চেক করার পর, min এবং max ভ্যালু পাস করে রিকার্শিভ মেথড isValidBST কল করি। যদি রুট ভ্যালু min-এর চেয়ে ছোট বা সমান এবং max-এর চেয়ে বড় বা সমান হয়, তবে এটি বাইনারি সার্চ ট্রি নয় বলে false রিটার্ন করি, অন্যথায় left এবং right ভ্যালু পাস করে isValidBST রিকার্শিভলি কল করি যতক্ষণ না সব নোড চেক হয়ে যায়।
উদাহরণ
public class TreesPgm
{
public class Node
{
public int Value;
public Node LeftChild;
public Node RightChild;
public Node(int value)
{
this.Value = value;
}
public override String ToString()
{
return "Node=" + Value;
}
}
public bool IsValidBST(Node root)
{
if (root == null)
{
return true;
}
return IsValidBST(root, int.MinValue, int.MaxValue);
}
private bool IsValidBST(Node root, int min, int max)
{
if (root == null)
{
return true;
}
if (root.Value <= min || root.Value >= max)
{
return false;
}
return IsValidBST(root.LeftChild, min, root.Value) && IsValidBST(root.RightChild, root.Value, max);
}
}ইনপুট
5
2 6
1 3আউটপুট
True