पता लगाएं कि बाइनरी पेड़ का लंबवत स्तर सी ++ में सॉर्ट किया गया है या नहीं

अवधारणा

किसी दिए गए बाइनरी ट्री के संबंध में, हमारा कार्य यह निर्धारित करना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल सॉर्ट किया गया है या नहीं।

(इस मामले के संबंध में, जब दो नोड्स ओवरलैप कर रहे हों, तो सत्यापित करें कि क्या वे उस स्तर पर क्रमबद्ध अनुक्रम बनाते हैं जो वे झूठ बोलते हैं।)

इनपुट

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