বাইনারি ট্রিতে এক রো নোড যোগ করা C++-এ

সমস্যা বিবরণ

একটি বাইনারি ট্রি, একটি ভ্যালু v এবং একটি গভীরতা d দেওয়া আছে। গভীরতা d-এ ভ্যালু v বিশিষ্ট নোডগুলোর একটি নতুন রো (row) যোগ করতে হবে। রুট নোড গভীরতা ১-এ আছে।

নিয়ম:

• গভীরতা d-1-এ থাকা প্রতিটি নোড N এর জন্য:
  • দুটি নতুন নোড (ভ্যালু v) তৈরি করুন — একটা বাম চাইল্ড, একটা ডান চাইল্ড।
  • N-এর মূল বাম সাবট্রি নতুন বাম নোডের বাম সাবট্রি হবে।
  • N-এর মূল ডান সাবট্রি নতুন ডান নোডের ডান সাবট্রি হবে।
• যদি d == 1 হয়, তবে নতুন নোডকে রুট বানিয়ে পুরনো ট্রিকে তার বাম সাবট্রি করুন।

উদাহরণ

ইনপুট ট্রি: [4,2,6,3,1,5], v = 1, d = 2

আউটপুট ট্রি: নতুন রো যোগ হওয়া ট্রি (লেভেল অর্ডার: [4,1,1,2,6,3,1,5])

অ্যালগরিদম: ইটারেটিভ DFS (স্ট্যাক ব্যবহার)

1. যদি d == 1: নতুন রুট তৈরি করে পুরনো রুটকে তার বামে লাগিয়ে দিন।
2. অন্যথায়:
   • স্ট্যাকে {root, 2} দিয়ে শুরু করুন (রুট লেভেল ১, এর চাইল্ডরা লেভেল ২)।
   • যখন level == d হয়, দুটি নতুন নোড বানিয়ে সংযুক্ত করুন।
   • অন্যথায় চাইল্ডদের স্ট্যাকে পুশ করুন লেভেল+১ দিয়ে।

C++ বাস্তবায়ন

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

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

class Solution {
public:
    TreeNode* addOneRow(TreeNode* root, int v, int d) {
        if (d == 1) {
            TreeNode* newRoot = new TreeNode(v);
            newRoot->left = root;
            return newRoot;
        }

        stack<pair<TreeNode*, int>> st;
        st.push({root, 2});

        while (!st.empty()) {
            auto [node, lvl] = st.top(); st.pop();
            if (lvl == d) {
                TreeNode* leftNode = new TreeNode(v);
                TreeNode* rightNode = new TreeNode(v);
                leftNode->left = node->left;
                rightNode->right = node->right;
                node->left = leftNode;
                node->right = rightNode;
            } else {
                if (node->left) st.push({node->left, lvl + 1});
                if (node->right) st.push({node->right, lvl + 1});
            }
        }
        return root;
    }
};

int main() {
    // ট্রি বানান এবং টেস্ট করুন
    return 0;
}

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

জটিলতা বিশ্লেষণ

• সময় জটিলতা: O(N) — সব নোড একবার ভিজিট করা হয়।
• স্থান জটিলতা: O(N) — স্ট্যাকে সবচেয়ে খারাপ কেসে O(N) নোড থাকতে পারে।