একটি অবিচ্ছিন্ন গাছকে একটি গাছ হিসাবে সংজ্ঞায়িত করা হয় যার রুট নোড থেকে লিফ নোড পর্যন্ত যে কোনও পথের মান বা নোডের ওজন থাকে যেমন প্যারেন্ট নোড এবং এর সমস্ত ডাইরেক্ট চিলড্রেন নোডের মধ্যে পরম পার্থক্য সর্বদা 1 হয়৷
যদি আমরা মূল থেকে পাতার পথে কোন নোড বাছাই করি, তাহলে
|নোডের ওজন-বাম শিশু নোডের ওজন|=|বাম শিশু নোডের ওজন-নোডের ওজন| =1, এটি সঠিক সন্তানের জন্যও সত্য
|নোডের ওজন-রাইট চাইল্ড নোডের ওজন|=|ওজন লফ রাইট চাইল্ড নোড-নোডের ওজন| =1
ডায়াগ্রাম
আসুন উদাহরণ দিয়ে বুঝতে পারি।
নীচের গাছটি অবিচ্ছিন্নভাবে প্যারেন্ট নোড এবং তাদের সন্তানের মধ্যে পরম পার্থক্য হিসাবে সর্বদা 1।
নীচের গাছটি একটি অবিচ্ছিন্ন গাছ হওয়ার জন্য যোগ্য নয়৷
গাছ ক্রমাগত কিনা তা খুঁজে বের করার অ্যালগরিদম
-
রুট NULL হলে, 1
ফেরত দিন -
যদি এটি একটি লিফ নোড হয়, তাহলে 1 ফেরত দিন কারণ গাছটি ক্রমাগত ছিল তাই পাতার নোডরেচ হয়েছে৷
-
যদি বাম সাবট্রি খালি থাকে তবে ডান চাইল্ডের সাথে বর্তমান নোডের ধারাবাহিকতা পরীক্ষা করুন (ওজনের পরম পার্থক্য গণনা করুন) এবং ডান সাবট্রির জন্য পুনরাবৃত্তিমূলকভাবে চালিয়ে যান।
-
যদি ডান সাবট্রিটি খালি থাকে তবে বাম সন্তানের সাথে বর্তমান নোডের ধারাবাহিকতা পরীক্ষা করুন (ওজনের পরম পার্থক্য গণনা করুন) এবং বাম সাবট্রির জন্য পুনরাবৃত্তিমূলকভাবে চালিয়ে যান।
-
অন্যথায় বাম এবং ডান সন্তানের ওজনের সাথে পরম পার্থক্য গণনা করুন এবং বাম এবং ডান উপবৃক্ষের জন্য চালিয়ে যান, পুনরাবৃত্তিমূলকভাবে।
সিউডোকোড
// Function to check tree is continuous or not
struct btreeNode{
int data;
btreeNode* left, * right;
};
int isContinuous(btreeNode *root){
// if node is NULL return 1, exit condition
if (root == NULL)
return 1;
//if leaf node is reached then tree must be continous during this path
if (root->left == NULL && root->right == NULL)
return 1;
// if no left child
if (root->left == NULL)
return (abs(root->data - root->right->data) == 1) && isContinuous(root->right);
// if no right child
if (root->right == NULL)
return (abs(root->data - root->left->data) == 1) && isContinuous(root->left);
// calculate absoute difference
return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 &&
isContinuous(root->left) && isContinuous(root->right);
} 