প্রদত্ত বাইনারি গাছের উল্লম্ব স্তরটি C++ এ সাজানো হয়েছে কিনা তা সন্ধান করুন

ধারণা

একটি প্রদত্ত বাইনারি গাছের ক্ষেত্রে, আমাদের কাজ হল বাইনারি গাছের প্রদত্ত উল্লম্ব স্তরটি সাজানো হয়েছে কিনা তা নির্ধারণ করা৷

(এই ক্ষেত্রে, যখন দুটি নোড ওভারল্যাপ করা হয়, তখন যাচাই করুন যে তারা যে স্তরে মিথ্যা বলছে সেখানে একটি সাজানো ক্রম তৈরি করে কিনা।)

ইনপুট

2
/ \
3 6
/ \
8 5
  /
7
Level l = -1

আউটপুট

Yes

লেভেল -1-এর নোডগুলি হল 3 -> 7 যা একটি সাজানো ক্রম তৈরি করে৷

ইনপুট

2
/ \
3 7
\ /
4 5
Level l = 0

আউটপুট

Yes

এটা উল্লেখ করা উচিত যে 4 এবং 5 মান সহ নোডগুলি বাইনারি ট্রিতে ওভারল্যাপ করছে৷

এখন আমরা যাচাই করি যে এই ফর্মটি একটি বাছাই করা ক্রম স্তর অনুসারে। লেভেল 0 এর নোড হল 2 -> 4 -> 5 যা একটি সাজানো সিকোয়েন্স তৈরি করে।

পদ্ধতি

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

দক্ষ সমাধান অনুসারে, আমরা বাইনারি গাছের উল্লম্ব স্তরের অর্ডার ট্রাভার্সাল করি এবং বাইনারি গাছের উল্লম্ব স্তর l-এ নোডের মানগুলির ট্র্যাক বজায় রাখি। পূর্ববর্তী উপাদান বর্তমান উপাদানের চেয়ে ছোট বা সমান হলে একটি সাজানো ক্রম তৈরি করা হয়। উল্লম্ব স্তরের অর্ডার ট্রাভার্সাল করার সময়, পূর্ববর্তী মান সংরক্ষণ করুন এবং উল্লম্ব স্তর l-এ বর্তমান নোডের তুলনা করুন লেভেল l-এর এই আগের মানের সাথে। এটা দেখা গেছে যে বর্তমান নোডের মান পূর্ববর্তী মানের থেকে বড় বা সমান হলে, লেভেল l শেষ না হওয়া পর্যন্ত একই পদ্ধতি পুনরাবৃত্তি করতে হবে। এটা দেখা গেছে যে কোন পর্যায়ে বর্তমান নোডের মান পূর্ববর্তী মানের থেকে ছোট হলে l স্তরটি সাজানো হয় না। আবার দেখা গেছে যে যদি আমরা লেভেল l এর শেষে পৌঁছাই তাহলে লেভেলটি সাজানো হয়।

উদাহরণ

// CPP program to determine whether
// vertical level l of binary tree
// is sorted or not.
#include <bits/stdc++.h>
using namespace std;
// Shows structure of a tree node.
struct Node1 {
   int key1;
   Node1 *left1, *right1;
};
// Shows function to create new tree node.
Node1* newNode(int key1){
   Node1* temp1 = new Node1;
   temp1->key1 = key1;
   temp1->left1 = temp1->right1 = NULL;
   return temp1;
}
// Indicates helper function to determine if
// vertical level l of given binary
// tree is sorted or not.
bool isSorted1(Node1* root1, int level1){
   // So If root is null, then the answer is an
   // empty subset and an empty subset is
   // always considered to be sorted.
   if (root1 == NULL)
      return true;
   // Indicates variable to store previous
   // value in vertical level l.
   int prevVal1 = INT_MIN;
   // Indicates variable to store current level
   // while traversing tree vertically.
   int currLevel1;
   // Indicates variable to store current node
   // while traversing tree vertically.
   Node1* currNode1;
   // Used to declare queue to do vertical order
   // traversal. A pair is used as element
   // of queue. The first element in pair
   // represents the node and the second
   // element represents vertical level
   // of that node.
   queue<pair<Node1*, int>> q1;
   // Used to insert root in queue. Vertical level
   // of root is 0.
   q1.push(make_pair(root1, 0));
   // Perform vertical order traversal until
   // all the nodes are not visited.
   while (!q1.empty()) {
      currNode1 = q1.front().first;
      currLevel1 = q1.front().second;
      q1.pop();
      // Verify if level of node extracted from
      // queue is required level or not. If it
      // is the required level then verify if
      // previous value in that level is less
      // than or equal to value of node.
      if (currLevel1 == level1) {
         if (prevVal1 <= currNode1->key1)
            prevVal1 = currNode1->key1;
      else
         return false;
   }
   // So if left child is not NULL then push it
   // in queue with level reduced by 1.
   if (currNode1->left1)
      q1.push(make_pair(currNode1->left1, currLevel1 - 1));
   // So if right child is not NULL then push it
   // in queue with level increased by 1.
   if (currNode1->right1)
      q1.push(make_pair(currNode1->right1, currLevel1 + 1));
   }
   // So if the level asked is not present in the
   // given binary tree, that means that level
   // will contain an empty subset. Therefore answer
   // will be true.
   return true;
}
// Driver program
int main(){
/*
      2
      / \
      3 6
      / \
      8 5
        /
      7
*/
   Node1* root1 = newNode(2);
   root1->left1 = newNode(3);
   root1->right1 = newNode(6);
   root1->left1->left1 = newNode(8);
   root1->left1->right1 = newNode(5);
   root1->left1->right1->left1 = newNode(7);
   int level1 = -1;
   if (isSorted1(root1, level1) == true)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

আউটপুট

Yes