Is it a Linearized Tree? (Breadth-first Edition)

Question

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]

Answer 1

Haskell, 44 bytes

f[n:k]=iterate f[k]!!n
f _=[]
g x=f[x]==[[]]

Defines a function g that takes a list and returns a boolean. See it pass all test cases.

Explanation

This relies on the fact that depth-first and breadth-first linearizations produce the same arrays. See Martin's answers for details; basically they both give the same arithmetical condition on the array.

The function f is given the input list wrapped in a singleton list. It pops one number n off the list, then calls itself n times on the remaining list to process the children of the popped node (depth first). Popping the empty list results in [], which I use as an error state. The function g checks that the end result is [[]], the unique non-erroneous state with no unprocessed nodes. If Haskell was weakly typed, I could just use 0 or something as the error state, and wouldn't have to wrap the input into another list.

Answer 2

Mathematica, 38 bytes

Last@#<0<=Min@Most@#&@Accumulate[#-1]&

The basic idea is that we keep track of a number of nodes to fill. Each element in the list uses up one node and adds as many as it has children. So each element i changes the total count by i-1. This count is off by one, because should be starting from 1 (the root), not 0.

For the tree to be valid we a) can never go below 0 throughout the list, because we wouldn't have anywhere to place the current node and b) need to end up with -1 at the end, otherwise we've got unused nodes left.

We obtain this running total of remaining nodes with Accumulate[#-1] (which computes the prefix sums of the input list minus one). And then we check that the last element and only the last element is -1 with:

Last@#<0<=Min@Most@#

Note that checking that the last element is negative is sufficient, since we can never decrement by more than 1, so if the last values was -2 or lower it would be impossible for the minimum the others to be non-negative.

Answer 3

Retina, 29 bytes

\d+
$*
^(?<-1>(1)*,)*$(?(1)!)

Try it online! (The first line enables a linefeed-separated test suite.)

Explanation

The basic idea is the same as that of my Mathematica answer: we keep track of a running total of remaining nodes, ensure it never goes below zero but ends on zero. However, the way this is implemented with regex is very different.

\d+
$*

This simply converts the input to unary, turning each integer n into n 1s.

^(?<-1>(1)*,)*$(?(1)!)

This is where the real magic happens. It's a fairly short regex that matches only valid trees, but it's mechanics are quite subtle.

I'm using balancing groups to keep track of the number of nodes, which are a way to work with stacks inside the regex.

First off, of course such a stack can never have a negative depth, so we can't really end up with a representation of -1 at the end, as we do in the Mathematica solution. However, we can note that the final element of the input has to be zero on a valid stack (otherwise we couldn't end up with -1). It turns out that it actually saves bytes to check both that we end on zero and with zero remaining nodes.

So here is a breakdown of the regex:

^        e# Anchor the match to the beginning of the string.
(?<-1>   e# Each repetition of this group will match one number. 
         e# We can ignore the <-1> for now.
  (1)*   e#   Match each unary digit of the current number, pushing
         e#   a capture onto stack 1. This increments our total of
         e#   remaining nodes by 1 for each child.
  ,      e#   Match a comma. Note that this requires that there is at
         e#   least one more number in the list.
)*       e# At the end of the repetition the <-1> pops one capture from
         e# the stack. This is the node that the current number itself
         e# takes up.
$        e# Match the end of the string. This requires the input to end
         e# in a zero, because the last thing we matched was a comma.
(?(1)!)  e# Make sure that stack 1 is empty, so that we don't have any
         e# unused nodes.

Answer 4

CJam (20 bytes)

{X0@{+\(_0>{\}*}/|!}

Online test suite. This is an anonymous block which takes an array on the stack and leaves 0 or 1 on the stack.

Dissection

In pseudocode this is:

p = 1
q = 0
foreach (i in input):
  q += i
  if (--p <= 0):      # in practice, if (--p == 0):
      p, q = q, p
return (p | q) == 0   # i.e. p == 0 && q == 0

q accumulates the sum of the labels of the nodes at the current level in the tree; p counts down the nodes remaining in the current level.

Answer 5

Labyrinth, 17 bytes

(
+?
;-)
,_"
@@,!

Try it online!

Truthy output is -1 and falsy output is empty. Defining truthy and falsy in Labyrinth is a bit tricky, because Labyrinth's branches are principally ternary. However, the only way to construct a conditional with reliably two branches, you can only do this:

>"F
 T

In this case, I'd consider moving straight ahead falsy (because the direction of movement is unaffected) and turning truthy. These correspond to zero and non-zero respectively. The reason I'm using an empty output to represent zero is that, if you were to pipe the output back into another Labyrinth program, the input operator ? would actually push a zero if the input is empty, so I consider the empty string a valid representation of zero.

Explanation

The algorithm is still the same as in my Mathematica and Retina answers, but due to Labyrinth's control flow, it works a bit different this time:

• We don't work with the total counter off-by-one here. Instead we a) work with a negative counter and b) initialise it to -11 initially, so that we want the counter to be negative throughout the list and hit zero on the last input. This actually simplifies the control flow here.

• Instead of building the full list and checking whether it contained the wrong value, there are three possible termination conditions:

  1. We hit EOF before reaching a total count of zero. In that case there are unused nodes left and we print nothing.
  2. We reach zero and we're at EOF. In this case, we've got a valid tree.
  3. We reach zero and aren't at EOF yet. In this case, we ran out of nodes before covering all elements, and we print nothing.

As for the actual code, we start in the top left corner. The ( turns the implicit zero on top of the stack into a -1, which will be the running total. We then enter the very tight main loop of the program, +?-)"_,;+:

+   Add the top two values. This does nothing on the first iteration,
    but gets rid of a helper-zero on subsequent iterations.
?   Read and push integer.
-   Subtract it from running total.
)   Increment.
"   No-op. There is a branch at this point. If the running total is zero,
    we move straight ahead onto the , (see below). Otherwise, the loop continues.
_   Push a zero. This is necessary to prevent the IP from turning south.
,   Read a character. This will either be the next separator (some positive
    number) or EOF (-1). If it's EOF, the IP turns south and the program
    terminates. Otherwise, the loop continues.
;   Discard the separator.

That leaves only the cases where we've reduced the running total to zero at some point. The IP moves onto the lower-right , and reads another character to check if we've reached EOF. If not, the value will be positive and the IP turns west towards the @ and the program terminates. If we did reach EOF, the IP turns east and prints the -1 with !. The IP will then worm its way towards the lower left @ via a slightly weird path to terminate the program.

Answer 6

Python, 82 bytes

lambda l:len(l)==sum(l)+1 and not any(list(l[x]>=len(l)-x for x in range(len(l))))

Need more test cases.

Answer 7

Pyth, 13 bytes

qxsM._tMQ_1tl

We start by calculating the current filled-ness of the tree at all points in the input representation. That portion of the idea is largely borrowed from Martin Ender, so thanks to him. sM._tMQ

Once we have this list, we check if the first index containing -1 (x..._1) is the length of the input minus one (q...tl(Q)).

Don't believe it works? Try it yourself!