C++-এ বাইনারি ট্রিতে দুটি লেভেলের মাঝপথে সব নোড প্রিন্ট করা

এই সমস্যায় একটি বাইনারি ট্রি এবং ট্রিতে দুটি লেভেল (উপরের এবং নিচের) দেওয়া আছে। আমাদের ট্রির উপরের এবং নিচের লেভেলের মাঝপথে সব নোড প্রিন্ট করতে হবে।

বাইনারি ট্রি হলো একটি বিশেষ ট্রি যেটির প্রতিটি নোডে সর্বোচ্চ দুটি নোড থাকে (একটি/দুটো/কোনোটিই নেই)।

উদাহরণ

উপরের লেভেল - 1

নিচের লেভেল - 3

আউটপুট -

6 3 9 7 4 8 10

এই সমস্যাটি সমাধানের জন্য ট্রির নির্দিষ্ট লেভেলের নোড প্রিন্ট করতে হবে। আমরা একটি রিকার্সিভ ফাংশন কল করব একটি লুপ দিয়ে উপরের থেকে নিচের লেভেল পর্যন্ত।

এই অ্যালগরিদম সহজ কিন্তু এর জটিলতা n²-এর কোটিতে।

একটি আরও কার্যকর সমাধান হচ্ছে ইন-অর্ডার ট্রাভার্সাল এবং একটি কিউ ব্যবহার করে। এবং দেওয়া উপরের ও নিচের লেভেলের মধ্যে থাকা নোডগুলো প্রিন্ট করা।

বাস্তবায়ন

#include <iostream> 
#include <queue> 
using namespace std; 

struct Node { 
    int key; 
    struct Node* left, *right; 
}; 

void printNodesAtLevel(Node* root, int low, int high) { 
    queue <Node *> Q; 
    Node *marker = new Node; 
    int level = 1; 
    Q.push(root); 
    Q.push(marker); 
    while (Q.empty() == false) { 
        Node *n = Q.front(); 
        Q.pop(); 
        if (n == marker) { 
            cout << endl; 
            level++; 
            if (Q.empty() == true || level > high) break; 
            Q.push(marker); 
            continue; 
        } 
        if (level >= low) 
            cout << n->key << " "; 
        if (n->left != NULL) Q.push(n->left); 
        if (n->right != NULL) Q.push(n->right); 
    } 
} 

Node* insertNode(int key) { 
    Node* temp = new Node; 
    temp->key = key; 
    temp->left = temp->right = NULL; 
    return (temp); 
} 

int main() { 
    struct Node *root = insertNode(6); 
    root->left = insertNode(3); 
    root->right = insertNode(9); 
    root->left->left = insertNode(7); 
    root->left->right = insertNode(4); 
    root->left->right->left = insertNode(8); 
    root->left->right->right = insertNode(10); 
    root->left->right->right->left = insertNode(5); 
    root->left->right->right->right = insertNode(1); 
    root->left->right->left->left = insertNode(14); 
    root->left->right->left->right = insertNode(26); 
    int upper = 3; 
    int lower = 1; 
    cout << "Level wise Nodes between level " << lower << " and " << upper << " are \n"; 
    printNodesAtLevel(root, lower, upper); 
    return 0; 
}

আউটপুট

Level wise Nodes between level 1 and 3 are
6 3 9 7 4