এই সমস্যায় একটি বাইনারি সার্চ ট্রি (BST) দেওয়া থাকলে, একটি নতুন নোড ইনসার্ট করতে হবে যাতে BST প্রপার্টি বজায় থাকে (বাম সাবট্রি < রুট < ডান সাবট্রি)।
সমাধানের পদ্ধতি (Recursive)
- যদি রুট
NULLহয়, নতুন নোড তৈরি করে রিটার্ন করুন। - যদি
val < root->val, বাম সাবট্রিতে রিকার্শিভলি ইনসার্ট করুন। - অন্যথায় ডান সাবট্রিতে রিকার্শিভলি ইনসার্ট করুন।
- রুট রিটার্ন করুন।
উদাহরণ (C++)
#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
if (root->val > val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
};
// Helper: Level order traversal for printing
void printLevelOrder(TreeNode* root) {
if (!root) return;
queue<TreeNode*> q;
q.push(root);
cout << "[";
while (!q.empty()) {
TreeNode* curr = q.front(); q.pop();
if (curr) {
cout << curr->val;
q.push(curr->left);
q.push(curr->right);
if (!q.empty()) cout << ", ";
} else {
cout << "null";
if (!q.empty()) cout << ", ";
}
}
cout << "]" << endl;
}
int main() {
// Building tree: [4,2,7,1,3]
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
Solution ob;
TreeNode* newRoot = ob.insertIntoBST(root, 5);
printLevelOrder(newRoot); // Expected: [4,2,7,1,3,5] (level order)
return 0;
}
ইনপুট
[4,2,7,1,3] 5
আউটপুট (Level Order)
[4, 2, 7, 1, 3, 5]
নোট: মূল কোডে লেভেল অর্ডার ট্রাভার্সালের জন্য কিউ এবং নাল মার্কার ব্যবহার করা হয়েছিল, যা কিছুটা জটিল। উপরে সহজ সংস্করণ দেওয়া হয়েছে।
