C++-এ দুটি বাইনারি সার্চ ট্রির সব উপাদান

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

তবে আউটপুট হবে [0,1,1,2,3,4]।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব -

• `ans` নামক একটি অ্যারে, দুটি স্ট্যাক `st1` এবং `st2` সংজ্ঞায়িত করুন
• `curr1 := root1` এবং `curr2 := root2`
• `root1` নোড এবং এর সব বাম নোডগুলো `st1`-এ ইনসার্ট করুন, `root2` নোড এবং এর সব বাম নোডগুলো `st2`-এ ইনসার্ট করুন
• যখন `st1` খালি না অথবা `st2` খালি না
  • যদি `st1` খালি না থাকে, এবং (`st2` খালি থাকে অথবা `st1`-এর টপ নোডের মান `<=` `st2`-এর টপ নোডের মান)
    • `temp := st1`-এর টপ, `st1`- থেকে নোড ডিলিট করুন
    • `temp`-এর মান `ans`-এ ইনসার্ট করুন
    • `temp`-এর ডান নোড এবং এর সব বাম নোডগুলো `st1`-এ ইনসার্ট করুন
  • অন্যথায় -
    • `temp := st2`-এর টপ, `st2`- থেকে নোড ডিলিট করুন
    • `temp`-এর মান `ans`-এ ইনসার্ট করুন
    • `temp`-এর ডান নোড এবং এর সব বাম নোডগুলো `st2`-এ ইনসার্ট করুন
• `ans` রিটার্ন করুন

উদাহরণ (C++)

বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন -

#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> 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 = NULL;          right = NULL;       } }; void insert(TreeNode **root, int val){    queue<TreeNode*> q;    q.push(*root);    while(q.size()){       TreeNode *temp = q.front();       q.pop();       if(!temp->left){          if(val != NULL)             temp->left = new TreeNode(val);          else             temp->left = new TreeNode(0);          return;       }       else{          q.push(temp->left);       }       if(!temp->right){          if(val != NULL)             temp->right = new TreeNode(val);          else             temp->right = new TreeNode(0);          return;       }       else{          q.push(temp->right);       }    } } TreeNode *make_tree(vector<int> v){    TreeNode *root = new TreeNode(v[0]);    for(int i = 1; i<v.size(); i++){       insert(&root, v[i]);    }    return root; } class Solution { public:    void pushLeft(stack <TreeNode*>& st, TreeNode* root){       TreeNode* curr = root;       while(curr){          st.push(curr);          curr = curr->left;       }    }    vector<int> getAllElements(TreeNode* root1, TreeNode* root2) {       vector <int> ans;       stack <TreeNode*> st1, st2;       TreeNode* curr1 = root1;       TreeNode* curr2 = root2;       pushLeft(st1, curr1);       pushLeft(st2, curr2);       while(!st1.empty() || !st2.empty()){          TreeNode* temp;          if(!st1.empty() && (st2.empty() || st1.top()->val <= st2.top()->val)){             temp = st1.top();             st1.pop();             ans.push_back(temp->val);             pushLeft(st1, temp->right);          }          else{             temp = st2.top();             st2.pop();             ans.push_back(temp->val);             pushLeft(st2, temp->right);          }       }       return ans;    } }; main(){    vector<int> v = {2,1,4};    TreeNode *root1 = make_tree(v);    v = {1,0,3};    TreeNode *root2 = make_tree(v);    Solution ob;    print_vector(ob.getAllElements(root1, root2)); }

ইনপুট

[2,1,4] [1,0,3]

আউটপুট

[0,1,1,2,3,4]