[Question]
  [
# Background
A **binary tree** is a rooted tree whose every node has at most two children.
A **labelled binary tree** is a binary tree whose every node is labelled with a positive integer; moreover, all labels are **distinct**.
A **BST** (binary search tree) is a labelled binary tree in which the label of each node is greater than the labels of all the nodes in its left subtree, and smaller than the labels of all the nodes in its right subtree. For instance, the following is a BST:
[![A BST](https://i.stack.imgur.com/i7c6d.png)](https://i.stack.imgur.com/i7c6d.png)
The **pre-order traversal** of a labelled binary tree is defined by the following pseudo-code.
```
function preorder(node)
    if node is null then
        return
    else
        print(node.label)
        preorder(node.left)
        preorder(node.right)
```
See the following image to get a better intuition:
[![Pre-order traversal of a BT](https://i.stack.imgur.com/kUMw1.png)](https://i.stack.imgur.com/kUMw1.png)
The vertices of this binary tree are printed in the following order:
```
F, B, A, D, C, E, G, I, H
```
You can read more about BSTs [here](https://en.wikipedia.org/wiki/Binary_search_tree), and more about pre-order traversal [here](https://en.wikipedia.org/wiki/Tree_traversal#Pre-order_(NLR)).
# Challenge
Given a list of integers \$a\$, your task is to determine whether there is a BST whose pre-order traversal prints exactly \$a\$.
## Input
* A non-empty **list** of distinct positive integers \$a\$.
* Optionally, the length of \$a\$.
## Output
* A **truthy** value if \$a\$ is the pre-order traversal of some BST.
* A **falsey** value otherwise.
# Rules
* **Standard rules** for [valid submissions](https://codegolf.meta.stackexchange.com/q/2419/82619), [I/O](https://codegolf.meta.stackexchange.com/q/2447/82619), [loopholes](https://codegolf.meta.stackexchange.com/q/1061/82619) apply.
* This is [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'"), so **shortest solution** (in bytes) wins. As usual, don't let ridiculously short solutions in golfy languages discourage you from posting a longer answer in your language of choice.
* This is not a rule, but your answer will be better received if it includes a link to test the solution and an explanation of how it works.
# Examples
```
Input                   ---->   Output
[1]                     ---->   True
[1,2,3,4]               ---->   True
[5,1,4,2,3]             ---->   True
[5,4,3,2,1,6,7,8,9]     ---->   True
[4,2,1,3,6,5,7]         ---->   True
[8,3,1,6,4,7,10,14,13]  ---->   True
[2,3,1]                 ---->   False
[6,3,2,4,5,1,8,7,9]     ---->   False
[1,2,3,4,5,7,8,6]       ---->   False
[3,1,4,2]               ---->   False
```
Check out [this link](https://pastebin.com/BFrtiM6Q) (courtesy of [Kevin Cruijssen](https://codegolf.stackexchange.com/users/52210/kevin-cruijssen)) to have a visual look at the examples.
  
[Answer]
# [JavaScript (Node.js)](https://nodejs.org), 49 bytes
```
a=>!a.some((p,i)=>a.some((q,j)=>q>p&a[j+=j>i]<p))
```
[Try it online!](https://tio.run/##fZFNS8MwGMfv@xTx4hL2LLNb9yKzuQgeRPSgtxlYqJm0dE3WxCmIn70@2VpBqcslBH7/X56XXO2VS6vM@mFpXnS9SWqViDPFndlqSi1kLBHtawc5vnbCnqtVPkhykckry1idmtJ54rXzqXLakYSse6tIkq4zxCPwfqreNEIwhgnE8iQ0hQjiAMqTUIymMaIzmMMCLmUHFB@ACSJTmMt/TAsEgiVGT3QBUQxR@Pk3FMru6LCFblThkJodSoohdLBA3Z@iGqoZQqgJqZnsdK2XvZ8Bc19lW8q4s0Xmaf@57DO@VZYWWalJIshnj5DjTlZtBoj@sDr1EpcTsCY7Gg7E6Bjeh@Tt48M9t6pymu65N3fmXVfXGKeMsWVjNYXmhXmlG9rKWWtH5ost628 "JavaScript (Node.js) – Try It Online")
Using the fact that for array \$a\_0 ... a\_{n-1}\$, \$a\$ is the pre-order traversal of some BST iff \$ \forall 0\le i<j<n; a\_i<a\_{j-1} \implies a\_i<a\_j \$ holds.
Thanks to [Arnauld](https://codegolf.stackexchange.com/users/58563/arnauld), save 1 byte.
[Answer]
# [Jelly](https://github.com/DennisMitchell/jelly), 7 bytes
```
ŒPŒ¿€4ḟ
```
[Try it online!](https://tio.run/##y0rNyan8///opICjkw7tf9S0xuThjvn/D7cDWUcnPdw54///6GjDWAUsgEsn2lDHSMdYxyQWQ8JUx1DHBCQZiyZsAlRvBJQ00zHXsdCxjIWIm4DFjIGipjrmsQj1FkAxkFoToGpDAx1DEx1D41igOMhWDEcBxc3AppvogKy3AOoBmo9wJchsoKhZbCwA "Jelly – Try It Online")
Returns `[4]` for traversals, otherwise `[]`.
Essentially uses tsh's algorithm: the "disqualifying" condition for a pre-order traversal is a [subsequence](https://en.wikipedia.org/wiki/Subsequence) of 3 elements that looks like **[mid, high, low]**. (For example, [20, 30, 10].)
We equivalently check for any subsequences of *any* length that have index **4** in their permutation lists, which are all lists sorted like **[a1 … ak c d b]** where the **ai** are sorted and **ai < b < c < d**. (Each such list is disqualifying if we look at the last three elements, and each disqualifying list is obviously of this form.)
```
ŒP          All subsequences.
  Œ¿€       Permutation index of each.
     4ḟ     Set difference of {4} and this list.
```
# Proof
> 
> ## A pre-order traversal contains no disqualifying subsequences
> 
> 
> Base case: **traversal(•)** is the empty list. ✓
> 
> 
> Induction: **traversal(t)** is: **t.root** ++ **traversal(t.left)** ++ **traversal(t.right)**.
> 
> 
> Let **[a, b, c]** be a subsequence hereof. We'll show **c < a < b** is impossible.
> 
> 
> * If **t.root = a**, then **c < a < b** requires **c ∈ t.left** and **b ∈ t.right**, so **[a, b, c]** is the wrong order.
> * If **a, b, c ∈ t.left** or **a, b, c ∈ t.right**, use the induction hypothesis.
> * If **a ∈ t.left** and **c ∈ t.right** then **c > a**.
> 
> 
> 
# 
> 
> ## A list of distinct integers without disqualifying subsequences is the pre-order traversal of a BST
> 
> 
> If the list is empty, it's the traversal of the trivial BST •.
> 
> 
> If the list is **head** followed by **tail**:
> 
> 
> * Let **less** be the longest prefix of **tail** of elements less than **head**, and let **more** be the rest of the list.
> * Then **more[1] > head**, and all other **more[i]** are greater than **head** too (otherwise **[head, more[1], more[i]]** would be a disqualifying subsequence).
> * Recurse: turn **less** and **more** into BSTs.
> * Now our list is the traversal of
> 
> 
> 
> ```
>                  head
>                 /    \
>          BST(less)   BST(more),
> 
> ```
> 
> and this tree is a valid BST.
> 
> 
> 
[Answer]
# Java 10, 94 bytes
```
a->{var r=0>1;for(int j=a.length-1,i;j-->0;)for(i=0;i<j;)r|=a[j]>a[i]&a[j+1]<a[i++];return!r;}
```
Port of [*@tsh*' JavaScript answer](https://codegolf.stackexchange.com/a/174295/52210).
[Try it online.](https://tio.run/##bZFNb8IwDIbv/ArvMrUiLQ2Ur4X2uNu4sBvqIZQA6UqK0hQJMX5752SwddKkRIr9xn4f2QU/86DYfrR5yesa3rhU1x6AVEboHc8FLG0IsKmqUnAFuYfSOgPuM8zf8OKpDTcyhyUoSKDlQXo9cw06iVLKdpW2JVAkPCyF2ptDQIlkRRCkEfOdmkRMLgrm68@Er4ss5WuZPeOrT7MFvvv9jGlhGq2eNLu1rIeOp2ZTouPd@FzJLRwR3VsZLdXe8X1zDwbwrhtzuLy40IjaeNSxPwIyJCMSd1NjQkls03@TMf4bojQhUzIj864YO2GE0phMu8IMk7YixhoaERoTars@0F55WYsummX5gzdxpjGxTDNsMv@H3ZqiOLmv5Hchbi7uJ24gDMOfqawutRHHsGpMeMKBmVJ5Ksw97t9b3Nov)
**Explanation:**
```
a->{                      // Method with integer-array parameter and boolean return-type
  var r=0>1;              //  Result-boolean, starting at false
  for(int j=a.length-1,i;j-->0;)
                          //  Loop `j` in the range (length-1, 0]:
    for(i=0;i<j;)         //   Inner loop `i` in the range [0, j):
      r|=                 //    If any are true, change the result to true as well:
         a[j]>a[i]        //     The `j`'th item is larger than the `i`'th item
         &a[j+1]<a[i++];  //     And the `j+1`'th item is smaller than the `i`'th item
  return!r;}              //  After the nested loop, check if the boolean is still false
```
[Answer]
# [Ruby](https://www.ruby-lang.org/), ~~46 40~~ 38 bytes
```
f=->r{a,*b=r;!a||b==b&[*0..a]|b&&f[b]}
```
[Try it online!](https://tio.run/##fdCxDoIwEAbg3adAByLkqFYqYkx18wnc6g2tkUmNKcHEUJ8drwQHDXJLly9//ztbmWfTFDLZ2lpDbKTdjLVzRkoTqnjOmEZnwrBQBl/NZKQ4Bn2T0GzpPdjqTAgWkILAQbQEDsJDHESCkhZEM1hBDmvsQaIFKZElrPBPUk7ApwjK4XPgArj/@Rv52j0bftBeX0pSWVtJgN8gp7ifUp3qjuA7kcqwN2vCypO@TWdHxeLdEWcRu@p77Up3D5SV54e@TMsICmWRzv8G "Ruby – Try It Online")
This works by recursively taking the first element `a` as a pivot, and checking if the rest of the array can be split in two (using intersection and union: first remove all elements >a, then add them again on the right and check if something has changed).
[Answer]
# [Retina 0.8.2](https://github.com/m-ender/retina/wiki/The-Language/a950ad7d925ec9316e3e2fb2cf5d49fd15d23e3d), 31 bytes
```
\d+
$*
M`\b((1+)1+,).*\1\2\b
^0
```
[Try it online!](https://tio.run/##NYwxDoMwEAT7e0ciGbxCnH0Y8wKq/OAUEZQUaVJE/N@5Q0o3s6vd7@t4fx7tGtat6TPSpafbpnsIHDuO6IZeWZPudB9bY2IkZAhNYIizkViSzAtmVCwkp2XzCTNVI@/EWh7BAs7kJ0zlHAr8rFq9/O99aEn5AQ "Retina 0.8.2 – Try It Online") Link includes test cases. Uses @tsh's algorithm. Explanation:
```
\d+
$*
```
Convert to unary.
```
M`\b((1+)1+,).*\1\2\b
```
Find numbers that lie between two subsequent consecutive descending numbers.
```
^0
```
Check that the number of matches is zero.
[Answer]
# [Perl 6](https://github.com/nxadm/rakudo-pkg), 38 bytes
```
!*.combinations(3).grep:{[>] .[1,0,2]}
```
[Try it online!](https://tio.run/##TY3dCoJAEIXvfYoNIjQO4uq6alIvIktYuCHkD9qNRM@@zWw33QxzPs58M3fLU7thEwcrzm53jO/TcOvH9tVP4xpmUfxYuvn0bi5GxI1EgtR8XB2s7SZsuL9Gwk5L0EgDGkiRQfGaQ0Jx/AVFPCWkUaBExVB5kBHKUTAoKXBDUUcmkArSX7PT67WXKLC7pFL195MlBLWp3Rc "Perl 6 – Try It Online")
### Explanation
```
 *.combinations(3)  # All combinations of 3 elements a,b,c
!                 .grep:{            }  # Return false if check succeeds for any combination
                         [>] .[1,0,2]   # Check whether b>a>c, that is b>a and c<a
```
[Answer]
# [Haskell](https://www.haskell.org/), 50 bytes
```
f[]=1<3
f(x:r)|(a,b)<-span(<x)r=all(>x)b&&f a&&f b
```
[Try it online!](https://tio.run/##jZDPCoJAEMbvPcUeQlYYodX1T6Uee4JusoeVWpI2Ey3w0LtvsxKBZeSwDHv4fvPNNyfZnY9aG6MKkbE02Crab1r3QSWUbup1jaxp2rttJrWmee@WjqOItK00F1nVJCOH64KQpq3qG1kSVTBBpsrz8OX42bf34xgAHwLgYjYQAgNuITEb4OjgIxZBDAmsxR@AD@IA5SHEYoZDgmI7neN8tgLGgdntfgM28sSl3sBO6m5MREMEDjZ9gjafIb6J12FtBiQiMelhng "Haskell – Try It Online")
[Answer]
# [05AB1E](https://github.com/Adriandmen/05AB1E/wiki/Commands), ~~15~~ 10 [bytes](https://github.com/Adriandmen/05AB1E/wiki/Codepage)
```
ŒεD{3.IÊ}P
```
Port of [*@Lynn*'s Jelly answer](https://codegolf.stackexchange.com/a/174306/52210).  
-5 bytes thanks to *@Emigna*.
[Try it online](https://tio.run/##yy9OTMpM/f//6KRzW12qjfU8D3fVBvz/H22hY6xjqGOmY6JjrmNooGNoomNoHAsA) or [verify all test cases](https://tio.run/##yy9OTMpM/V9Waa@k8KhtkoKSfeX/o5PObXWpNtbzPNxVG/Bf5390tGGsjkK0oY6RjrGOCYhpqmOoYwLiQjgmQHEjoJCZjrmOhY4lSNAELGAMFDLVMQcJWAA5IBUmQDWGBjqGJjqGYN0gM8HGm4ENMdEBmW0BVGSJZCfIEKCgWWwsAA).
**Explanation:**"
```
Œ             # Take all sublists of the (implicit) input-list
              #  i.e. [2,3,1] → [[2],[2,3],[2,3,1],[3],[3,1],[1]]
              #  i.e. [1,2,3,4]
              #   → [[1],[1,2],[1,2,3],[1,2,3,4],[2],[2,3],[2,3,4],[3],[3,4],[4]]
 ε      }     # Map each to:
  D           #  Duplicate the current sublist on the stack
   {          #  Sort the copy
              #   i.e. [2,3,1] → [1,2,3]
              #   i.e. [2,3,4] → [2,3,4]
    3.I       #  Get the 4th (3rd 0-indexed) permutation of this list
              #   i.e. [1,2,3] → [2,3,1]
              #   i.e. [2,3,4] → [3,4,2]
       Ê      #  Check that the lists are NOT equal
              #   i.e. [2,3,1] and [2,3,1] → 0 (falsey)
              #   i.e. [2,3,4] and [3,4,2] → 1 (truthy)
         P    # Check whether all are truthy (and output implicitly)
              #  i.e. [1,1,0,1,1,1] → 0 (falsey)
              #  i.e. [1,1,1,1,1,1,1,1,1,1] → 1 (truthy)
```
[Answer]
# Scala (68 67 Bytes)
```
def%(i:Seq[Int])= !i.combinations(3).exists(c=>c(0)<c(1)&c(0)>c(2))
```
[Try it online](https://tio.run/##dY8/D4IwEMV3P0VdTJtcCIXyz4iJo4OTo3HAUpIaLGg7kBg/O14ZBbfr/d6792pl1VZjd7sr6cip0oaowSlTW3Loe/Iea9WQhurtWT0vR@OurCRrHcjucdOmcrozlsYsUIO2zlJZ7iUN2U5SzjZ@wmfE2Ni/tHGtoQ3FM8gYW/2sIIIYxBwkwEF4uIQEeiIUpJBBDsVcIiYcoyCBbI5zRN4t0M9D4AL4Qo5vtlA5ncIF@IY5Hij@/sqHoyT1gs/4BQ)
Port of @nwellnhof's [answer](https://codegolf.stackexchange.com/a/174310/83520).
# Scala (122 103 bytes)
```
def f(i:Seq[Int]):Boolean=if(i.size<1)1>0 else{val(s,t)=i.tail.span(_<i(0));t.forall(_>i(0))&f(s)&f(t)}
```
Thanks to @Laikoni for the suggestions to make both solutions shorter.
[Try it online](https://tio.run/##dY/NasMwEITvfQqdygoWYyWK4/xCeuuhpx5LCUqyAgUhO5EIoSHP7q58rN2LDvPNaGbj0XjTNYczHZP4MC4IuicKpyh2bSse3YmssOCWn3T5eg/pWy7fmsaTCRvHchHdD62VVNtSkI/0uBkPEZPcuCIZ54vYmgD7tYNSylUqbHM13sN@2wuvFmJ@knx27dWF5ANY4CZQUsqXPxJOcIp6CGaoUGc4hjRnJmyocI41LoYW3eMpG2Y4H@KaUU5rzqsSlUY10pOXjUyu@nKNeWHNHyz@vSqXs6XKhmf3Cw)
### Explanation:
1. slice (using Scala's `span`) the array using array's head as the slicing criteria.
2. Confirm that the first slice of the array is less than the head and the second slice is greater than the head.
3. recursively check that each slice also satisfies (2)
[Answer]
# [Haskell](https://www.haskell.org/), 41 bytes
```
f(h:t)=t==[]||all(>h)(snd$span(<h)t)&&f t
```
[Try it online!](https://tio.run/##jZDNDoIwEITvPkUPhtBkSSyUH41w9Am8kR6aAIFYkUC98e64RWOCotDsoYf5dnamlN0lV2oYCrs8aBrrOE5F30ul7KSkdldn266RtX0sqaaWVRA9XGVVk5hktw0hTVvVmmxJkTJB5p7j4CT4Obf3fAqACx5wsRrwgQE3kFgNcHRwEQsghAj2YgHgo9hDuQ@hWOEQodhs57if7YBxYOa634CJPNPUGzhJ1U2JYIzAwaSP0OYzxDfxKtZkQCIQyx7es1nx96rhAQ "Haskell – Try It Online")
Uses [Lynn's observation](https://codegolf.stackexchange.com/a/174306/20260) that it suffices to check that there's no subsequence of the for **mid..high..low**. This means that for each element `h`, the list of elements `t` that comes after is a block of elements `<h` followed by a block of elements `>h` (both blocks may be empty). So, the code checks that after we drop the prefix of elements `<h` in `t`, the remaining elements are all `>h`. Recursing checks this for each initial element `h` until the list is length 1.
A potential simplification is that it suffices to check for subpatterns **mid..high,low** where the last two are consecutive. Unfortunately, Haskell's doesn't have an short way to extract the last two elements, as can be done from the front with a pattern match `a:b:c`. I found a shorter solution that checks for **mid,high..low**, but this fails to reject inputs like `[3,1,4,2]`.
Formatted test cases taken [from Laikoni](https://codegolf.stackexchange.com/a/174318/20260).
[Answer]
# [Japt](https://github.com/ETHproductions/japt), 14 bytes
```
d@sY ð_§XÃxÈ-Y
```
[Japt Interpreter](https://ethproductions.github.io/japt/?v=1.4.6&code=ZEBzWSDwX6dYw3jILVk=&input=WzYsMywyLDQsNSwxLDgsNyw5XQ==)
Outputs `false` for BST, `true` for no BST.
Explanation:
```
d@                Run on each item X, return true if any aren't 0: 
  sY                  Ignore the numbers before this index
     ð_§XÃ            Get the indexes of numbers less than or equal to X
                          If it is a BST, this list will be e.g. [0,1,2...]
            -Y        Subtract the position within the index list from each index
                          eg. [0,1,2] -> [0,0,0] , [0,1,4] -> [0,0,2]
          xÈ          Sum the resulting array
```
[Answer]
# Scala
All approaches are implementations of the rule shown by tsh.
# 109
```
l.zipWithIndex.foldLeft(1>0){case(r,(v,i))=>r&l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)}
```
# 101
```
(for(i<-l.indices)yield l.zip(l.tail).slice(i+1,l.size).forall(x =>l(i)>x._1|l(i)<x._2)).forall(x=>x)
```
# 98
```
l.indices.foldLeft(1>0)((r,i)=>r&(l.zip(l.tail).slice(i+1,l.size).forall(x=>l(i)>x._1|l(i)<x._2)))
```
# 78
```
(for(i<-l.indices;j<-i+1 to l.size-2)yield l(i)>l(j)|l(i)<l(j+1)).forall(x=>x)
```
If it must be a function and not just an expression then each line have to start with (17 bytes)
```
def%(l:Seq[Int])=
```
[Answer]
# [Husk](https://github.com/barbuz/Husk), 10 bytes
```
Λo≠4Ṡ€oPOQ
```
[Try it online!](https://tio.run/##yygtzv7//9zs/EedC0we7lzwqGlNfoB/4P///6ONdIx1DGMB "Husk – Try It Online")
Same idea as Kevin Cruijssen's answer.
[Answer]
# Oracle SQL, 177 bytes
```
with r(i,v)as(select rownum,value(t)from table(a)t)
select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,(select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
```
Since there is no boolean type in Oracle SQL, query returns either 1 or 0.
# Oracle SQL 12c, 210 bytes
```
with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)from(select value(t)c from table(powermultiset_by_cardinality(a,3))t)
```
It's not possible access element of the array in SQL the same way as in PL/SQL - i.e. a(i), thus function `f` was declared in `with clause` for that purpose. Otherwise solution would have been much shorter.
Other limitations
* throws an exception for arrays shorter than 3 elements (instead of returning 1)
* there is an assumption that powermultiset\_by\_cardinality preserves order even though it's not explicitly stated in the documentation
**sqlplus** listing
```
SQL> set heading off
SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(6,3,2,4,5,1,8,7,9))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /
                                            0
SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(6,3,2,4,5,1,8,7,9),3))t)
  4  /
                                                     0
SQL> with r(i,v)as(select rownum,value(t)from table(ku$_objnumset(8,3,1,6,4,7,10,14,13))t)
  2  select nvl(min(case when r.v<p.l and r.v>p.v then 0end),1)from r,
  3  (select i,lag(v)over(order by i)l,v from r)p where r.i+1<p.i
  4  /
                                            1
SQL> with function f(n ku$_objnumset,i int)return int as begin return n(i);end;
  2  select min(case when f(c,1)>f(c,2)or f(c,1)<f(c,3)then 1else 0end)
  3  from(select value(t)c from table(powermultiset_by_cardinality(ku$_objnumset(8,3,1,6,4,7,10,14,13),3))t)
  4  /
                                                     1
```
Online verification [apex.oracle.com](http://apex.oracle.com)
**Update**
# Oracle SQL, 155 bytes
```
with r(i,v)as(select rownum,value(t)from table(a)t)select nvl(min(case when a.v<b.v and a.v>c.v then 0end),1)r from r a,r b,r c where a.i<b.i and b.i+1=c.i
```
[Answer]
# **C, 823 bytes** (not counting whitespace characters); 923 bytes (including whitespace)
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{struct tree * left;struct tree * right;int val;}tree;static int * test_p = 0;
void insert_root(tree ** root, int in)
{if (*root == NULL){*root = (tree *)calloc(1,sizeof(tree));(*root)->val = in;return;}else if (in < (*root)->val){insert_root(&((*root)->left),in);}else{insert_root(&((*root)->right),in);}}
void preorder(tree * root)
{if ( root == 0x0 ) { return; }*test_p++ = root->val;preorder(root->left);preorder(root->right);}
int main(int argc, char ** argv)
{int test_list[argc-1];memset(test_list,0,argc*sizeof(int));test_p = test_list;tree * root = (tree *)calloc(1,sizeof(tree));root->val = strtol(argv[1],0x0,10);int i = 1;while ( argv[++i] != 0x0 ){insert_root(&root,strtol(argv[i],0x0,10));}preorder(root);test_p = test_list;i = 1;while ( ( i < argc ) ){if ( *test_p != strtol(argv[i],0x0,10) ){return 0;}test_p++;i++;}return 1;}
```
The readable version of the program is below:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct tree
{
    struct tree * left;
    struct tree * right;
    int val;
} tree;
static int * test_p = 0;
void insert_root(tree ** root, int in)
{
  if (*root == NULL)
  {
    *root = (tree *)calloc(1,sizeof(tree));
    (*root)->val = in;
    return;
  }
  else if (in < (*root)->val)
  {
    insert_root(&((*root)->left),in);
  }
  else
  {
    insert_root(&((*root)->right),in);
  }
}
void preorder(tree * root)
{
    if ( root == 0x0 ) {  return; }
    
        *test_p++ = root->val;
        preorder(root->left);
        preorder(root->right);
}
int main(int argc, char ** argv)
{
    int test_list[argc-1];
    memset(test_list,0,argc*sizeof(int));
    
    test_p = test_list;
    
    tree * root = (tree *)calloc(1,sizeof(tree));
    root->val = strtol(argv[1],0x0,10);
    int i = 1;
    while ( argv[++i] != 0x0 )
    {
        insert_root(&root,strtol(argv[i],0x0,10));
    }
    
    preorder(root);
    
    test_p = test_list;
    i = 1;
    while ( ( i < argc ) )
    {
        if ( *test_p != strtol(argv[i],0x0,10) )
        {
            return 0;
        }
        test_p++;
        i++;
    }
    return 1;   
}
```
The main method in this program reads the list of numbers that are (allegedly) a legitimate preorder traversal.
The function insert\_root that is called inserts the integers into a binary search tree where previous nodes contain lesser values and next nodes contain larger int values.
The function preorder(root) traverses the tree in a preorder traversal and simultaneously concatenates each integer the algorithm comes across to the int array **test\_list**.
A final while loop tests if each of the int values in the **stdin** list and those in **test\_list** are equivalent at each index. If there is a list element from **stdin** that fails to match the corresponding element in test\_list at the respective index, the main function **returns 0.** Else the main method **returns 1**.
To determine what main returned, type **echo $status** into the bash terminal. BASH will either print out a 1 or a 0.
[Answer]
# [Husk](https://github.com/barbuz/Husk), 9 bytes
```
¬ṁ§=Oṙ2Ṗ3
```
[Try it online!](https://tio.run/##RY2xDQIxDEUX@gVOfLlcwQwMEKU/CVEhBjiGQGICGhZIe5uERcx3KOj@f7af19v1bJfPfbP93du2v46n3p6ht0c0s1KkoggCIpRpgkC9jaykgSRhRsZCpqNHkgkze2b2uXJDDhCF@KnrXJyGQOHazJXl/8wFZIkk/p7W@gU "Husk – Try It Online")
Uses 'disqualifying condition' of any subsequence mid...high...low from [tsh's](https://codegolf.stackexchange.com/a/174295/95126) and [Lynn's](https://codegolf.stackexchange.com/a/174306/95126) answers.
```
¬ṁ§=Oṙ2Ṗ3
       Ṗ3   # consider all subsequences of length 3:
     ṙ2     # check whether rotating 2 to the left
  §=O       # is the same as sorting;
¬ṁ          # total of subsequences that satisfy this should be zero
```
]