প্রোগ্রামটি একটি বাইনারি ট্রির মিডল লেভেল (middle level) প্রিন্ট করবে। উদাহরণস্বরূপ, ৪ লেভেল থাকলে লেভেল ২ প্রিন্ট করবে — কিন্তু হাইট বের না করে।
পারফেক্ট বাইনারি ট্রি (Perfect Binary Tree): যেই ট্রিতে সব ইন্টিয়র নোডের দুটি চাইল্ড থাকে এবং সব লিফ নোড একই লেভেল/ডেপথে থাকে।
- ইন্টিয়র নোড ২১ এবং ৩২ — দুটোরই চাইল্ড আছে।
- লিফ নোড ৪১, ৫৯, ৩৩, ৭০ — সবই একই লেভেলে।
উদাহরণ
Input: 12 21 32 41 59 33 70 Output: 21 32
অ্যাপ্রোচ: লিংকড লিস্টের মিডল এলিমেন্ট বের করার মতোই — লেফট এবং রাইট পয়েন্টার NULL কিনা চেক করে রিকার্সিভ কল দিয়ে মিডল লেভেল বের করা যায়।
অ্যালগরিদম
START
Step 1: Create node structure with key, left, right
Step 2: Function New(int value) to create node
Step 3: Function middle(Node* a, Node* b)
IF a==NULL || b==NULL RETURN
IF (b->left==NULL && b->right==NULL)
PRINT a->key; RETURN
CALL middle(a->left, b->left->left)
CALL middle(a->right, b->left->left)
Step 4: Function mid_level(Node* node)
CALL middle(node, node)
Step 5: In main()
Create tree, call mid_level(root)
STOP
সি প্রোগ্রাম
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
struct Node* left, *right;
};
struct Node* New(int value) {
struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
temp->key = value;
temp->left = temp->right = NULL;
return temp;
}
void middle(struct Node* a, struct Node* b) {
if (a == NULL || b == NULL) return;
if ((b->left == NULL) && (b->right == NULL)) {
printf("%d ", a->key);
return;
}
middle(a->left, b->left->left);
middle(a->right, b->left->left);
}
void mid_level(struct Node* node) {
middle(node, node);
}
int main() {
printf("middle level nodes are: ");
struct Node* n1 = New(13);
struct Node* n2 = New(21);
struct Node* n3 = New(44);
struct Node* n4 = New(98);
struct Node* n5 = New(57);
struct Node* n6 = New(61);
struct Node* n7 = New(70);
n2->left = n4; n2->right = n5;
n3->left = n6; n3->right = n7;
n1->left = n2; n1->right = n3;
mid_level(n1);
return 0;
}
আউটপুট
middle level nodes are: 21 44
