C++-এ বাইনারি ট্রির বাম দিকের ভিউ (Left Side View) বের করার প্রোগ্রাম

সমস্যা বিবরণ

একটি বাইনারি ট্রি বাম দিক থেকে দেখলে যেসব নোড দেখা যায়, সেগুলো বের করতে হবে। অর্থাৎ, প্রতিটি লেভেলের সবচেয়ে বামের নোড।

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

সমাধানের পদ্ধতি (DFS - Preorder Traversal)

1. একটি ভেক্টর ret এবং একটি ভেরিয়েবল lvl = -1 রাখুন।
2. DFS ফাংশন লিখুন যা নোড এবং বর্তমান লেভেল c নেবে।
3. যদি নোড NULL হয়, রিটার্ন করুন।
4. যদি c > lvl হয়, তবে:
   • lvl = c
   • নোডের ভ্যালু ret-এ পুশ করুন।
5. পहলে লেফ্ট সাবট্রি, তারপর রাইট সাবট্রি-তে রিকার্সিভ কল দিন (c+1 পাস করে)।
6. মেইন থেকে dfs(root, 0) কল করুন এবং ret রিটার্ন করুন।

নোট: বাম সাবট্রি আগে ট্রাভার্স করলে প্রতিটি লেভেলের প্রথম নোডই বাম দিক থেকে দেখা যাবে।

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 ret;
    int lvl;
    void dfs(TreeNode* node, int c = 1) {
        if (!node) return;
        if (c > lvl) {
            lvl = c;
            ret.push_back(node->val);
        }
        dfs(node->left, c + 1);
        dfs(node->right, c + 1);
    }
    vector solve(TreeNode* root) {
        lvl = -1;
        dfs(root, 0);
        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, 5]

জটিলতা

• সময়: O(n)
• স্থান: O(h) — h = ট্রির উচুতা (রিকার্সন স্ট্যাক)