C++-এ বাইনারি ট্রির লেভেল অর্ডার ট্রাভার্সাল প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি দেওয়া থাকলে, এর লেভেল অর্ডার ট্রাভার্সাল (Level Order Traversal) বা ব্রেডথ-ফার্স্ট সার্চ (BFS) করুন। অর্থাৎ, লেভেল বাই লেভেল বাম থেকে ডানে নোডগুলো ভিজিট করুন।

উদাহরণ: রুট=১, লেফ্ট=২, রাইট=৩, ২-এর রাইট=৫, ৩-এর রাইট=৪ → ট্রাভার্সাল: [1, 2, 3, 5, 4]

সমাধানের পদ্ধতি

1. একটি কিউ que তৈরি করুন।
2. রুট কিউতে পুশ করুন।
3. যতক্ষন কিউ খালি নয়:
   • ফ্রন্ট নোড বের করুন।
   • এর ভ্যালু প্রিন্ট/স্টোর করুন।
   • লেফ্ট চাইল্ড থাকলে কিউতে পুশ করুন।
   • রাইট চাইল্ড থাকলে কিউতে পুশ করুন।
   • ফ্রন্ট এলিমেন্ট পপ করুন।

C++ কোড উদাহরণ

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << ", ";
    }
    cout << "]" << endl;
}

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) {
        val = data;
        left = right = NULL;
    }
};

class Solution {
public:
    vector solve(TreeNode* root) {
        if (!root) return {};
        vector ret;
        queue q;
        q.push(root);
        while (!q.empty()) {
            TreeNode* node = q.front(); q.pop();
            ret.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        return ret;
    }
};

int main() {
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(4);
    Solution ob;
    print_vector(ob.solve(root));
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: বর্ণিত ট্রি

আউটপুট: [1, 2, 3, 5, 4, ]

জটিলতা

• সময়: O(n)
• স্থান: O(w) — w = সর্বোচ্চ উইডথ