সি প্রোগ্রামিং-এ বাইনারি ট্রির দিয়ে गये লেভেলের লিফ নোড প্রিন্ট করা

বাইনারি ট্রির নির্দিষ্ট লেভেল k-তে থাকা লিফ নোডগুলো প্রিন্ট করতে হবে।

লিফ নোড (Leaf Node): যেসব নোডের লেফট এবং রাইট পয়েন্টার NULL থাকে, অর্থাৎ সেগুলো কোনো পেরেন্ট নোড নয়।

উদাহরণ

Input: 11 22 33 66 44 88 77
Output: 88 77

এখানে k নির্দিষ্ট লেভেল যেটা প্রিন্ট করতে হবে। অ্যাপ্রোচ: প্রতিটি নোড ট্রাভার্স করে চেক করা হয় কি এর কোনো চাইল্ড আছে। যদি একটাও চাইল্ড থাকে, তবে সেটি লিফ নোড নয়। লেভেল অর্ডার ট্রাভার্সাল (Level Order Traversal) ব্যবহার করে রিকার্সিভলি নোডগুলো ভিজিট করা হয়।

অ্যালগরিদম

START
Step 1: Create node structure with data, left, right
Step 2: Function New(int data) to create node
Step 3: Function leaf(node* root, int level)
    IF root == NULL RETURN
    IF level == 1
        IF root->left == NULL && root->right == NULL
            PRINT root->data
    ELSE IF level > 1
        CALL leaf(root->left, level-1)
        CALL leaf(root->right, level-1)
Step 4: In main()
    level = 4, create tree, call leaf(root, level)
STOP

সি প্রোগ্রাম

#include <stdio.h>
#include <stdlib.h>

struct node {
    struct node* left;
    struct node* right;
    int data;
};

struct node* New(int data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

void leaf(struct node* root, int level) {
    if (root == NULL) return;
    if (level == 1) {
        if (root->left == NULL && root->right == NULL)
            printf("%d\n", root->data);
    } else if (level > 1) {
        leaf(root->left, level - 1);
        leaf(root->right, level - 1);
    }
}

int main() {
    printf("leaf nodes are: ");
    struct node* root = New(11);
    root->left = New(22);
    root->right = New(33);
    root->left->left = New(66);
    root->right->right = New(44);
    root->left->left->left = New(88);
    root->left->left->right = New(77);
    int level = 4;
    leaf(root, level);
    return 0;
}

আউটপুট

leaf nodes are: 88 77