Is this a BST pre-order traversal?

Clash Royale CLAN TAG#URR8PPP

up vote
4
down vote

favorite

1

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 an 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:

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:

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, and more about pre-order traversal here.

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 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, I/O, loopholes apply.


• This is 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

Check out this link (courtesy of Kevin Cruijssen) to have a visual look at the examples.

code-golf decision-problem binary-tree

share|improve this question

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
  – Kevin Cruijssen
  1 hour ago
  
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

1

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 an 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:

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:

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, and more about pre-order traversal here.

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 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, I/O, loopholes apply.


• This is 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

Check out this link (courtesy of Kevin Cruijssen) to have a visual look at the examples.

code-golf decision-problem binary-tree

share|improve this question

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
  – Kevin Cruijssen
  1 hour ago
  
  

  
  
  
  

add a comment | 

up vote
4
down vote

favorite

1

up vote
4
down vote

favorite

1

1

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 an 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:

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:

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, and more about pre-order traversal here.

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 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, I/O, loopholes apply.


• This is 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

Check out this link (courtesy of Kevin Cruijssen) to have a visual look at the examples.

code-golf decision-problem binary-tree

share|improve this question

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

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 an 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:

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:

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, and more about pre-order traversal here.

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 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, I/O, loopholes apply.


• This is 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

Check out this link (courtesy of Kevin Cruijssen) to have a visual look at the examples.

code-golf decision-problem binary-tree

code-golf decision-problem binary-tree

share|improve this question

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

share|improve this question

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

share|improve this question

share|improve this question

edited 1 hour ago

edited 1 hour ago

edited 1 hour ago

asked 1 hour ago

Delfad0r

1,053213

asked 1 hour ago

Delfad0r

1,053213

asked 1 hour ago

Delfad0r

1,053213

1,053213

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
  – Kevin Cruijssen
  1 hour ago
  
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
  – Kevin Cruijssen
  1 hour ago
  
  

  
  
  
  

1

1

Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
– Kevin Cruijssen
1 hour ago

Here a pastebin of the test cases to have a more visual look as to how they are truthy/falsey. Nice challenge btw, +1 from me.
– Kevin Cruijssen
1 hour ago

add a comment | 

2 Answers
2

active

oldest

votes

up vote
3
down vote

JavaScript (Node.js), 50 bytes

a=>!a.some((p,i)=>a.some((q,j)=>j>i&q>p&a[j+1]<p))

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 0le i<j<n; a_i<a_j implies a_i<a_j+1 $ holds.

share|improve this answer

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

add a comment | 

up vote
2
down vote

Retina 0.8.2, 31 bytes

d+
$*
M`b((1+)1+,).*12b
^0

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

d+
$*

Convert to unary.

M`b((1+)1+,).*12b

Find numbers that lie between two subsequent consecutive descending numbers.

^0

Check that the number of matches is zero.

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

add a comment | 

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "200"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174293%2fis-this-a-bst-pre-order-traversal%23new-answer', 'question_page');

);

Post as a guest

Name Email

2 Answers
2

active

oldest

votes

2 Answers
2

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
3
down vote

JavaScript (Node.js), 50 bytes

a=>!a.some((p,i)=>a.some((q,j)=>j>i&q>p&a[j+1]<p))

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 0le i<j<n; a_i<a_j implies a_i<a_j+1 $ holds.

share|improve this answer

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

add a comment | 

up vote
3
down vote

JavaScript (Node.js), 50 bytes

a=>!a.some((p,i)=>a.some((q,j)=>j>i&q>p&a[j+1]<p))

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 0le i<j<n; a_i<a_j implies a_i<a_j+1 $ holds.

share|improve this answer

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

add a comment | 

up vote
3
down vote

up vote
3
down vote

JavaScript (Node.js), 50 bytes

a=>!a.some((p,i)=>a.some((q,j)=>j>i&q>p&a[j+1]<p))

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 0le i<j<n; a_i<a_j implies a_i<a_j+1 $ holds.

share|improve this answer

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

JavaScript (Node.js), 50 bytes

a=>!a.some((p,i)=>a.some((q,j)=>j>i&q>p&a[j+1]<p))

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 0le i<j<n; a_i<a_j implies a_i<a_j+1 $ holds.

share|improve this answer

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

share|improve this answer

share|improve this answer

edited 13 mins ago

edited 13 mins ago

edited 13 mins ago

answered 32 mins ago

tsh

7,69111344

answered 32 mins ago

tsh

7,69111344

answered 32 mins ago

tsh

7,69111344

7,69111344

add a comment | 

add a comment | 

up vote
2
down vote

Retina 0.8.2, 31 bytes

d+
$*
M`b((1+)1+,).*12b
^0

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

d+
$*

Convert to unary.

M`b((1+)1+,).*12b

Find numbers that lie between two subsequent consecutive descending numbers.

^0

Check that the number of matches is zero.

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

add a comment | 

up vote
2
down vote

Retina 0.8.2, 31 bytes

d+
$*
M`b((1+)1+,).*12b
^0

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

d+
$*

Convert to unary.

M`b((1+)1+,).*12b

Find numbers that lie between two subsequent consecutive descending numbers.

^0

Check that the number of matches is zero.

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

add a comment | 

up vote
2
down vote

up vote
2
down vote

Retina 0.8.2, 31 bytes

d+
$*
M`b((1+)1+,).*12b
^0

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

d+
$*

Convert to unary.

M`b((1+)1+,).*12b

Find numbers that lie between two subsequent consecutive descending numbers.

^0

Check that the number of matches is zero.

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

Retina 0.8.2, 31 bytes

d+
$*
M`b((1+)1+,).*12b
^0

Try it online! Link includes test cases. Uses @tsh's algorithm. Explanation:

d+
$*

Convert to unary.

M`b((1+)1+,).*12b

Find numbers that lie between two subsequent consecutive descending numbers.

^0

Check that the number of matches is zero.

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

share|improve this answer

share|improve this answer

answered 12 mins ago

Neil

76.6k744173

answered 12 mins ago

Neil

76.6k744173

answered 12 mins ago

Neil

76.6k744173

76.6k744173

add a comment | 

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodegolf.stackexchange.com%2fquestions%2f174293%2fis-this-a-bst-pre-order-traversal%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email