snipt

Ctrl+h for KB shortcuts

C++

BST

#include<bits/stdc++.h>
using namespace std;
//https://www.geeksforgeeks.org/check-given-array-can-represent-level-order-traversal-binary-search-tree/
struct df{
    int d;
    int mn,mx;
};
bool checkforlevelorder(int arr[],int n){
if(n == 0){
    return true;
}
queue<df>q;
int i = 0;
df newnode;
newnode.d = arr[i++];
newnode.mn = INT_MIN;
newnode.mx = INT_MAX;
q.push(newnode);
while(i != n && !q.empty()){
    df temp = q.front();
    q.pop();
    if(i < n && arr[i] > temp.mn && arr[i] < temp.mx){
        df tempnode;
        tempnode.d = arr[i++];
        tempnode.mn = temp.mn;
        tempnode.mx = temp.d;
        q.push(tempnode);
    }
    if(i < n && arr[i] > temp.mn && arr[i] < temp.mx){
        df tempnode;
        tempnode.d = arr[i++];
        tempnode.mn = temp.d;
        tempnode.mx = temp.mx;
        q.push(tempnode);
    }  

}
if(i == n){return true;}
return false;
}
int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i < n;i++){cin>> arr[i];}
    if(checkforlevelorder(arr,n)){cout << "yes";}
    else{cout << "No"<< endl;}
    return 0;
}
https://snippets.siftie.com/embed/dad8f939b8c0e45783660a4f88bdbaca/
/raw/dad8f939b8c0e45783660a4f88bdbaca/
dad8f939b8c0e45783660a4f88bdbaca
cpp
C++
50
2019-04-20T16:40:57
True
False
False
Feb 19, 2019 at 10:56 AM
/api/public/snipt/148265/
to-check-an-array-is-level-order-traversal-or-not
<table class="highlighttable"><tr><td class="linenos"><div class="linenodiv"><pre><a href="#L-1"> 1</a> <a href="#L-2"> 2</a> <a href="#L-3"> 3</a> <a href="#L-4"> 4</a> <a href="#L-5"> 5</a> <a href="#L-6"> 6</a> <a href="#L-7"> 7</a> <a href="#L-8"> 8</a> <a href="#L-9"> 9</a> <a href="#L-10">10</a> <a href="#L-11">11</a> <a href="#L-12">12</a> <a href="#L-13">13</a> <a href="#L-14">14</a> <a href="#L-15">15</a> <a href="#L-16">16</a> <a href="#L-17">17</a> <a href="#L-18">18</a> <a href="#L-19">19</a> <a href="#L-20">20</a> <a href="#L-21">21</a> <a href="#L-22">22</a> <a href="#L-23">23</a> <a href="#L-24">24</a> <a href="#L-25">25</a> <a href="#L-26">26</a> <a href="#L-27">27</a> <a href="#L-28">28</a> <a href="#L-29">29</a> <a href="#L-30">30</a> <a href="#L-31">31</a> <a href="#L-32">32</a> <a href="#L-33">33</a> <a href="#L-34">34</a> <a href="#L-35">35</a> <a href="#L-36">36</a> <a href="#L-37">37</a> <a href="#L-38">38</a> <a href="#L-39">39</a> <a href="#L-40">40</a> <a href="#L-41">41</a> <a href="#L-42">42</a> <a href="#L-43">43</a> <a href="#L-44">44</a> <a href="#L-45">45</a> <a href="#L-46">46</a> <a href="#L-47">47</a> <a href="#L-48">48</a> <a href="#L-49">49</a></pre></div></td><td class="code"><div class="highlight"><pre><span></span><span id="L-1"><a name="L-1"></a><span class="cp">#include</span><span class="cpf">&lt;bits/stdc++.h&gt;</span><span class="cp"></span> </span><span id="L-2"><a name="L-2"></a><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span> </span><span id="L-3"><a name="L-3"></a><span class="c1">//https://www.geeksforgeeks.org/check-given-array-can-represent-level-order-traversal-binary-search-tree/</span> </span><span id="L-4"><a name="L-4"></a><span class="k">struct</span> <span class="n">df</span><span class="p">{</span> </span><span id="L-5"><a name="L-5"></a> <span class="kt">int</span> <span class="n">d</span><span class="p">;</span> </span><span id="L-6"><a name="L-6"></a> <span class="kt">int</span> <span class="n">mn</span><span class="p">,</span><span class="n">mx</span><span class="p">;</span> </span><span id="L-7"><a name="L-7"></a><span class="p">};</span> </span><span id="L-8"><a name="L-8"></a><span class="kt">bool</span> <span class="nf">checkforlevelorder</span><span class="p">(</span><span class="kt">int</span> <span class="n">arr</span><span class="p">[],</span><span class="kt">int</span> <span class="n">n</span><span class="p">){</span> </span><span id="L-9"><a name="L-9"></a><span class="k">if</span><span class="p">(</span><span class="n">n</span> <span class="o">==</span> <span class="mi">0</span><span class="p">){</span> </span><span id="L-10"><a name="L-10"></a> <span class="k">return</span> <span class="nb">true</span><span class="p">;</span> </span><span id="L-11"><a name="L-11"></a><span class="p">}</span> </span><span id="L-12"><a name="L-12"></a><span class="n">queue</span><span class="o">&lt;</span><span class="n">df</span><span class="o">&gt;</span><span class="n">q</span><span class="p">;</span> </span><span id="L-13"><a name="L-13"></a><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-14"><a name="L-14"></a><span class="n">df</span> <span class="n">newnode</span><span class="p">;</span> </span><span id="L-15"><a name="L-15"></a><span class="n">newnode</span><span class="p">.</span><span class="n">d</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="o">++</span><span class="p">];</span> </span><span id="L-16"><a name="L-16"></a><span class="n">newnode</span><span class="p">.</span><span class="n">mn</span> <span class="o">=</span> <span class="n">INT_MIN</span><span class="p">;</span> </span><span id="L-17"><a name="L-17"></a><span class="n">newnode</span><span class="p">.</span><span class="n">mx</span> <span class="o">=</span> <span class="n">INT_MAX</span><span class="p">;</span> </span><span id="L-18"><a name="L-18"></a><span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">newnode</span><span class="p">);</span> </span><span id="L-19"><a name="L-19"></a><span class="k">while</span><span class="p">(</span><span class="n">i</span> <span class="o">!=</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="o">!</span><span class="n">q</span><span class="p">.</span><span class="n">empty</span><span class="p">()){</span> </span><span id="L-20"><a name="L-20"></a> <span class="n">df</span> <span class="n">temp</span> <span class="o">=</span> <span class="n">q</span><span class="p">.</span><span class="n">front</span><span class="p">();</span> </span><span id="L-21"><a name="L-21"></a> <span class="n">q</span><span class="p">.</span><span class="n">pop</span><span class="p">();</span> </span><span id="L-22"><a name="L-22"></a> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">temp</span><span class="p">.</span><span class="n">mn</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">temp</span><span class="p">.</span><span class="n">mx</span><span class="p">){</span> </span><span id="L-23"><a name="L-23"></a> <span class="n">df</span> <span class="n">tempnode</span><span class="p">;</span> </span><span id="L-24"><a name="L-24"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">d</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="o">++</span><span class="p">];</span> </span><span id="L-25"><a name="L-25"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">mn</span> <span class="o">=</span> <span class="n">temp</span><span class="p">.</span><span class="n">mn</span><span class="p">;</span> </span><span id="L-26"><a name="L-26"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">mx</span> <span class="o">=</span> <span class="n">temp</span><span class="p">.</span><span class="n">d</span><span class="p">;</span> </span><span id="L-27"><a name="L-27"></a> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">tempnode</span><span class="p">);</span> </span><span id="L-28"><a name="L-28"></a> <span class="p">}</span> </span><span id="L-29"><a name="L-29"></a> <span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&gt;</span> <span class="n">temp</span><span class="p">.</span><span class="n">mn</span> <span class="o">&amp;&amp;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">]</span> <span class="o">&lt;</span> <span class="n">temp</span><span class="p">.</span><span class="n">mx</span><span class="p">){</span> </span><span id="L-30"><a name="L-30"></a> <span class="n">df</span> <span class="n">tempnode</span><span class="p">;</span> </span><span id="L-31"><a name="L-31"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">d</span> <span class="o">=</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="o">++</span><span class="p">];</span> </span><span id="L-32"><a name="L-32"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">mn</span> <span class="o">=</span> <span class="n">temp</span><span class="p">.</span><span class="n">d</span><span class="p">;</span> </span><span id="L-33"><a name="L-33"></a> <span class="n">tempnode</span><span class="p">.</span><span class="n">mx</span> <span class="o">=</span> <span class="n">temp</span><span class="p">.</span><span class="n">mx</span><span class="p">;</span> </span><span id="L-34"><a name="L-34"></a> <span class="n">q</span><span class="p">.</span><span class="n">push</span><span class="p">(</span><span class="n">tempnode</span><span class="p">);</span> </span><span id="L-35"><a name="L-35"></a> <span class="p">}</span> </span><span id="L-36"><a name="L-36"></a> </span><span id="L-37"><a name="L-37"></a><span class="p">}</span> </span><span id="L-38"><a name="L-38"></a><span class="k">if</span><span class="p">(</span><span class="n">i</span> <span class="o">==</span> <span class="n">n</span><span class="p">){</span><span class="k">return</span> <span class="nb">true</span><span class="p">;}</span> </span><span id="L-39"><a name="L-39"></a><span class="k">return</span> <span class="nb">false</span><span class="p">;</span> </span><span id="L-40"><a name="L-40"></a><span class="p">}</span> </span><span id="L-41"><a name="L-41"></a><span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span> </span><span id="L-42"><a name="L-42"></a> <span class="kt">int</span> <span class="n">n</span><span class="p">;</span> </span><span id="L-43"><a name="L-43"></a> <span class="n">cin</span> <span class="o">&gt;&gt;</span> <span class="n">n</span><span class="p">;</span> </span><span id="L-44"><a name="L-44"></a> <span class="kt">int</span> <span class="n">arr</span><span class="p">[</span><span class="n">n</span><span class="p">];</span> </span><span id="L-45"><a name="L-45"></a> <span class="k">for</span><span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span><span class="n">i</span> <span class="o">&lt;</span> <span class="n">n</span><span class="p">;</span><span class="n">i</span><span class="o">++</span><span class="p">){</span><span class="n">cin</span><span class="o">&gt;&gt;</span> <span class="n">arr</span><span class="p">[</span><span class="n">i</span><span class="p">];}</span> </span><span id="L-46"><a name="L-46"></a> <span class="k">if</span><span class="p">(</span><span class="n">checkforlevelorder</span><span class="p">(</span><span class="n">arr</span><span class="p">,</span><span class="n">n</span><span class="p">)){</span><span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&quot;yes&quot;</span><span class="p">;}</span> </span><span id="L-47"><a name="L-47"></a> <span class="k">else</span><span class="p">{</span><span class="n">cout</span> <span class="o">&lt;&lt;</span> <span class="s">&quot;No&quot;</span><span class="o">&lt;&lt;</span> <span class="n">endl</span><span class="p">;}</span> </span><span id="L-48"><a name="L-48"></a> <span class="k">return</span> <span class="mi">0</span><span class="p">;</span> </span><span id="L-49"><a name="L-49"></a><span class="p">}</span> </span></pre></div> </td></tr></table>
1
2
3
4
5
6
7
8
9
--- 
+++ 
@@ -1,5 +1,6 @@
 #include<bits/stdc++.h>
 using namespace std;
+//https://www.geeksforgeeks.org/check-given-array-can-represent-level-order-traversal-binary-search-tree/
 struct df{
     int d;
     int mn,mx;
--- 
+++ 
@@ -0,0 +1,48 @@
+#include<bits/stdc++.h>
+using namespace std;
+struct df{
+    int d;
+    int mn,mx;
+};
+bool checkforlevelorder(int arr[],int n){
+if(n == 0){
+    return true;
+}
+queue<df>q;
+int i = 0;
+df newnode;
+newnode.d = arr[i++];
+newnode.mn = INT_MIN;
+newnode.mx = INT_MAX;
+q.push(newnode);
+while(i != n && !q.empty()){
+    df temp = q.front();
+    q.pop();
+    if(i < n && arr[i] > temp.mn && arr[i] < temp.mx){
+        df tempnode;
+        tempnode.d = arr[i++];
+        tempnode.mn = temp.mn;
+        tempnode.mx = temp.d;
+        q.push(tempnode);
+    }
+    if(i < n && arr[i] > temp.mn && arr[i] < temp.mx){
+        df tempnode;
+        tempnode.d = arr[i++];
+        tempnode.mn = temp.d;
+        tempnode.mx = temp.mx;
+        q.push(tempnode);
+    }  
+
+}
+if(i == n){return true;}
+return false;
+}
+int main(){
+    int n;
+    cin >> n;
+    int arr[n];
+    for(int i = 0;i < n;i++){cin>> arr[i];}
+    if(checkforlevelorder(arr,n)){cout << "yes";}
+    else{cout << "No"<< endl;}
+    return 0;
+}