একটি কন্টিনিউআস ট্রি হলো এমন ট্রি যেখানে রুট থেকে লিফ নোড পর্যন্ত যেকোনো পথে প্যারেন্ট নোড এবং তার সরাসরি চাইল্ড নোডের ওয়েটের আসল পার্থক্য (absolute difference) সবসময় ১ থাকে।
অর্থাৎ, যেকোনো নোডের জন্য: |weight(node) - weight(left child)| = 1 এবং |weight(node) - weight(right child)| = 1।
অ্যালগরিদম: ট্রি কন্টিনিউআস কিনা যাচাই
- যদি root == NULL, return true (1)।
- যদি লিফ নোড হয়, return true (এই পথে কন্টিনিউইটি রক্ষা হয়েছে)।
- যদি লেফট সাবট্রি খালি হয়, করেন্ট নোড ও রাইট চাইল্ডের পার্থক্য ১ কিনা চেক করে রাইট সাবট্রির জন্য রিকার্সিভ কল।
- যদি রাইট সাবট্রি খালি হয়, করেন্ট নোড ও লেফট চাইল্ডের পার্থক্য ১ চেক করে লেফট সাবট্রির জন্য রিকার্সিভ কল।
- অন্যথায়, উভয় চাইল্ডের সাথে পার্থক্য ১ এবং উভয় সাবট্রি রিকার্সিভলি কন্টিনিউআস কিনা চেক।
পসিউডোকোড
struct btreeNode{
int data;
btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
if (root == NULL) return 1;
if (root->left == NULL && root->right == NULL) return 1;
if (root->left == NULL)
return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
if (root->right == NULL)
return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
return abs(root->data - root->left->data)==1 &&
abs(root->data - root->right->data)==1 &&
isContinuous(root->left) &&
isContinuous(root->right);
}চিত্রগুলো কন্টিনিউআস এবং নন-কন্টিনিউআস ট্রির উদাহরণ দেখাচ্ছে।
