11
1
Background
An unlabelled tree may look like this:
o
/ | \
o o o
| / \
o o o
To linearize this tree, we first label each node o
with it's number of child nodes:
3
/ | \
1 0 2
| / \
0 0 0
and then write the numbers in a list in a breath-first manner, meaning line by line and left to right:
[3, 1, 0, 2, 0, 0, 0]
This is a unique and unambiguous representation of the tree above, meaning that no two different pure trees will have the same linearizations and that we can reconstruct the original tree from the list.
Although each tree corresponds to a certain integer list, not each integer list represents a valid linearized tree: For example [2, 0, 0, 0]
does not represent a valid tree, if we try to de-linearize it we end up with this tree
[2,0,0,0] -> 2 [0,0,0] -> 2 [0,0] -> 2 [0]
/ \ / \ / \
0 0 0
but still have a 0
left in the list and nowhere to put it. Similarly [2, 0]
is not a valid tree linearization either, as the de-linearized tree has an empty child spot:
2
/ \
0
Task
Given an integer list, decide whether it is a valid linearization of a tree using as few bytes as possible. You may write a full program or a function.
Input: A non-empty list of non-negative integers.
Output: A truthy value if the list is a linearization of a tree, a falsy value otherwise.
Testcases
Truthy[0]
[2, 0, 0]
[1, 1, 1, 1, 1, 0]
[3, 1, 0, 2, 0, 0, 0]
[2, 0, 2, 2, 0, 0, 2, 0, 0]
[3, 2, 2, 1, 1, 1, 0, 0, 0, 0, 0]
[1, 5, 3, 0, 2, 1, 4, 0, 1, 0, 0, 2, 1, 0, 0, 1, 1, 0, 0, 0, 0, 2, 1, 0, 0, 1, 0]
Falsy
[0, 1]
[2, 0]
[2, 0, 0, 0]
[1, 0, 1]
[3, 2, 1, 0]
[2, 0, 0, 2, 0, 0]
[4, 1, 0, 3, 0, 0, 0, 0]
[4, 2, 0, 3, 1, 0, 0, 0, 0, 0]
{X0@{+\(_{\}&}/|!}
I think? – Martin Ender – 2016-11-24T23:46:16.307Also it seems like you should be able to save a byte by using a full program to avoid the
@
. – Martin Ender – 2016-11-24T23:51:38.547