તપાસો કે આપેલ એરે બાઈનરી શોધ ટ્રીના લેવલ ઓર્ડર ટ્રversવર્સલનું પ્રતિનિધિત્વ કરી શકે છે  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે એમેઝોન સિટ્રીક્સ IBM ખરેખર માહિતી એજ ઓયો ઓરડાઓ તેરાદાતા
દ્વિસંગી શોધ વૃક્ષ દ્વિસંગી વૃક્ષ કતાર વૃક્ષ વૃક્ષ આડેધડ

સમસ્યા નિવેદન  

સમસ્યા "તપાસો કે જો આપેલ એરે બાઈનરી સર્ચ ટ્રીના લેવલ ઓર્ડર ટ્રાવેર્સલનું પ્રતિનિધિત્વ કરી શકે છે" કહે છે કે તમને સ્તરનું ઓર્ડર ટ્રાવર્સલ આપવામાં આવ્યું છે દ્વિસંગી શોધ વૃક્ષ. અને ની મદદથી લેવલ ઓર્ડર ટ્રાવર્સલ ઝાડની. આપણે કાર્યક્ષમ રીતે શોધવાની જરૂર છે કે શું લેવલ ઓર્ડર ટ્રversવર્સલ દ્વિસંગી શોધ વૃક્ષનું પ્રતિનિધિત્વ કરી શકે છે કે નહીં?

ઉદાહરણ  

Level Order Traversal - {5 2 7 1 6 9 }
True

 

તપાસો કે આપેલ એરે બાઈનરી શોધ ટ્રીના લેવલ ઓર્ડર ટ્રversવર્સલનું પ્રતિનિધિત્વ કરી શકે છેપિન

સમજૂતી

આપેલ સ્તરનું ઓર્ડર ટ્ર .વર્સલ દ્વિસંગી વૃક્ષનું પ્રતિનિધિત્વ કરે છે જે છબીમાં બતાવવામાં આવ્યું છે. અને આપણે જોઈ શકીએ છીએ કે ઝાડ દ્વિસંગી ઝાડની બધી મિલકતોને સંતોષે છે અને આમ આઉટપુટ સાચું છે.

આપેલ એરે બાઈનરી સર્ચ ટ્રીના લેવલ ઓર્ડર ટ્રાવેર્સલનું પ્રતિનિધિત્વ કરી શકે છે કે કેમ તેની તપાસ માટેનો અભિગમ  

નિષ્કપટ અભિગમ

નિષ્કપટ અભિગમ હોઇ શકે જો આપણે આપેલા તમામ બાઈનરી ટ્રી બનાવવાનો પ્રયત્ન કરીએ જે આપેલા લેવલ ઓર્ડરને આડઅસરને સંતોષે. અને પછી તપાસો કે શું વૃક્ષ દ્વિસંગી શોધ વૃક્ષનું પ્રતિનિધિત્વ કરે છે. પરંતુ આ કામગીરી ખૂબ મોંઘી થશે. સૌ પ્રથમની જેમ, અમે પણ ઘણાં વૃક્ષોનું નિર્માણ કરીશું. પછી અલ્ગોરિધમનો તપાસ કરવાની જરૂર છે કે રચેલું વૃક્ષ બીએસટી છે કે નહીં. તેથી, આપણે કંઈક કરવાની જરૂર છે જ્યાં અમને વૃક્ષ બનાવવાની જરૂર નથી.

આ પણ જુઓ
આપેલ લિંક્ડ સૂચિના અંતથી Nth નોડ કા Deleteી નાખો

કાર્યક્ષમ અભિગમ

એક કાર્યક્ષમ અભિગમ સ્તરના ક્રમમાં આક્રમણ થતાં દરેક તત્વો માટેની સીમાઓ સંગ્રહિત કરશે. આ સીમાઓ તે સીમાને રજૂ કરે છે જેમાં તેમના સબટ્રી તત્વો ખોટા બોલી શકે છે. જો આપણે નોડ વિશે વાત કરીશું, તો તેમાં ઓછામાં ઓછું અને મહત્તમ હશે. ડાબી સબટ્રીમાં ન્યૂનતમ બાઉન્ડથી વર્તમાન નોડ વેલ્યુ -1 સુધીના ઘટકો હોઈ શકે છે. જ્યારે જમણા સબટ્રીના તત્વો વર્તમાન નોડ મૂલ્ય +1 થી મહત્તમ બાઉન્ડ સુધીના હોઈ શકે છે.

તેથી, અમે એક કતારનો ઉપયોગ કરીશું જ્યાં આપણે આ સીમાઓ સાથે તત્વો દાખલ કરવાનું ચાલુ રાખીશું અને જો આપણે બધા ગાંઠોમાંથી પસાર થઈ શકશું. અમે કહીએ છીએ કે આપેલ લેવલ ઓર્ડર ટ્રાવર્સલ બીએસટીનું પ્રતિનિધિત્વ કરી શકે છે નહીં કે નહીં. અલ્ગોરિધમનો દ્વિસંગી વૃક્ષ બીએસટી છે કે નહીં તે તપાસવા જેવું જ છે.

કોડ  

સી ++ કોડ તપાસવા માટે કે આપેલ એરે બાઈનરી સર્ચ ટ્રીના લેવલ ઓર્ડર ટ્રversવર્સલનું પ્રતિનિધિત્વ કરી શકે છે

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    int mn;
    int mx;
};

node create(int data, int mn, int mx){
    node tmp;
    tmp.data = data;
    tmp.mn = mn;
    tmp.mx = mx;
    return tmp;
}

bool checkLevelOrderTraversalRepresentBinarySearchTree(vector<int> traversal){
    queue<node> q;
    int i = 0, n = traversal.size();
    q.push(create(traversal[i++], INT_MIN, INT_MAX));

    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
            q.push(create(traversal[i++], now.mn, now.data));
        if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
            q.push(create(traversal[i++], now.data, now.mx));
    }
    return (i == n);
}

int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> traversal(n);
        for(int i=0;i<n;i++)
            cin>>traversal[i];
        cout<<(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no")<<endl;
    }
}
1
6
5 2 7 1 6 9
true

જાવા કોડ એ ચકાસવા માટે કે આપેલ એરે બાઈનરી સર્ચ ટ્રીના લેવલ ઓર્ડર ટ્ર Traવર્સલનું પ્રતિનિધિત્વ કરી શકે છે

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int mn;
  int mx;
}

class Main{
  
  static node create(int data, int mn, int mx){
      node tmp = new node();
      tmp.data = data;
      tmp.mn = mn;
      tmp.mx = mx;
      return tmp;
  }
  
  static boolean checkLevelOrderTraversalRepresentBinarySearchTree(int traversal[]){
      Queue<node> q = new LinkedList<node>();
      int i = 0; int n = traversal.length;
      q.add(create(traversal[i++], Integer.MIN_VALUE, Integer.MAX_VALUE));
  
      while(q.size() > 0){
          node now = q.peek();
          q.remove();
          if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
              q.add(create(traversal[i++], now.mn, now.data));
          if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
              q.add(create(traversal[i++], now.data, now.mx));
      }
      return (i == n);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-- > 0){
          int n = sc.nextInt();
          int[] traversal = new int[n];
          for(int i=0;i<n;i++)
              traversal[i] = sc.nextInt();
          System.out.println(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no");
      }
  }
}
1
6
5 2 7 1 6 9
true

જટિલતા વિશ્લેષણ  

સમય જટિલતા

જેમ આપણે તત્વો ઉપર સરળતાથી પસાર થઈ ગયા છે. અને સૌથી ખરાબ કિસ્સામાં, આપણે બધા તત્વોને ઓળંગી જવાની જરૂર છે, એલ્ગોરિધમમાં રેખીય સમયની જટિલતા છે ઓ (એન)

આ પણ જુઓ
ડુપ્લિકેટ સબટ્રીઝ શોધો

અવકાશ જટિલતા

અમે તત્વોને સંગ્રહિત કરવા માટે કતારનો ઉપયોગ કર્યો છે જેણે રેખીય જગ્યાની જટિલતાને માટે અલ્ગોરિધમનો બનાવ્યો હતો ઓ (એન).