C++-এ বাইনারি ট্রিয়ের দ্বিতীয় ন্যূনতম নোড (Second Minimum Node In a Binary Tree)

একটি নন-খালি স্পেশাল বাইনারি ট্রি দেওয়া আছে যেখানে প্রতিটি নোডে নন-নেগেটিভ মান আছে। প্রতিটি নোডের বা ০ বা ২টি চাইল্ড থাকে। যদি ২টি চাইল্ড থাকে, তবে নোডের মান তার দুটি চাইল্ডের ন্যূনতম মান। অর্থাৎ root.val = min(root.left.val, root.right.val)। এমন একটি বাইনারি ট্রি দিয়ে পুরো ট্রির নোড মানগুলোর সেট থেকে দ্বিতীয় ন্যূনতম মান বের করতে হবে। না থাকলে -1 রিটার্ন করবে।

ইনপুট ট্রি দেখুন চিত্রে। আউটপুট ৫। ন্যূনতম মান ২, দ্বিতীয় ন্যূনতম ৫।

সমাধানের ধাপসমূহ

TraverseNodes() ফাংশন: নোড, min, nextMin নেয়
যদি নোড null হয়, রিটার্ন
যদি নোডের মান > min হয়, nextMin আপডেট করুন
বাম ও ডান সাবট্রি রিকার্শিভলি ট্রাভার্স করুন
মূল ফাংশন থেকে min := root.val, nextMin := -1, TraverseNodes কল করুন, nextMin রিটার্ন করুন

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
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; ival != 0) ? root->val : -1;
        int nextMin = -1;
        TraverseNodes(root, min, nextMin);
        return nextMin;
    }
    void TraverseNodes(TreeNode* node, int min, int& nextMin) {
        if (!node || node->val == 0) {
            return;
        }
        if (node->val > min) {
            if (nextMin == -1 || node->val < nextMin) {
                nextMin = node->val;
            }
        }
        TraverseNodes(node->left, min, nextMin);
        TraverseNodes(node->right, min, nextMin);
    }
};
int main(){
    Solution ob;
    vector<int> v = {2,2,5,NULL,NULL,5,7};
    TreeNode *root = make_tree(v);
    cout << (ob.findSecondMinimumValue(root));
}

ইনপুট

{2,2,5,NULL,NULL,5,7}