Decide Contiguous Binary Tree

Question

Objective

Given an unlabelled binary tree, decide whether it is contiguous in indices.

Indices

This challenge gives one-indexing on binary trees. The exact definition expresses all indices in binary numeral:

• The root is indexed 1.

• For every node, to get the index of its left child, replace the most significant 1 by 10.

• For every node, to get the index of its right child, replace the most significant 1 by 11.

For illustration: Binary tree indexing

A binary tree is contiguous in indices iff the indices of its nodes have no gaps.

Note that every binary tree with contiguous indices is balanced.

I/O Format

Flexible.

Examples

L indicates a leaf. [ , ] indicates a branch.

Truthy

L
[L,L]
[[L,L],L]
[[L,L],[L,L]]
[[[L,L],L],[L,L]]
[[[L,L],L],[[L,L],L]]

Falsy

[L,[L,L]]
[[[L,L],L],L]
[[[L,L],[L,L]],[L,L]]
[[[L,L],L],[L,[L,L]]]

• Unrelated String: Assuming solutions have to handle unbalanced trees, it would help to have one in the falsy test cases.
• Dannyu NDos: @alephalpha Nodes are branches; leaves don't count as nodes.
• David G.: The test cases do not include any nodes with one child, like: [L,] or [[L,],[L,L]] Note that this could break some parsers based on the existing test cases.
• Dannyu NDos: @DavidG. Nodes are branches; leaves don't count as nodes.
• David G.: @DannyuNDos But a binary tree can have 2 entries in it. In a binary tree, there is normally an entry in each leaf and each branch node.

Answer 1

Jelly, (削除) 11 (削除ここまで) (削除) 10 (削除ここまで) (削除) 9 (削除ここまで) (削除) 8 (削除ここまで) 7 bytes

ŒṪ’UḄṬP

Try it online!

-1 thanks to Jonathan Allan--funny that I used ŒṪ earlier, but never tried removing Ż with it

(削除) Very (削除ここまで) Embarrassingly naive solution, using ŒṪ "generate multidimensional truthy indices" to directly produce the indices, then Ṭ "untruth" to lay them out... if I was sure it works at all, since this doesn't actually produce the stated labeling scheme or represent non-leaf nodes at all. I actually thought it didn't work for a bit, but then I realized my counterexample wasn't a binary tree to begin with.

Requires that the leaf value is truthy.

ŒJ Generate multidimensional 1-indices of truthy values.
 ’ Decrement to 0-indices,
 U and reverse, so the deepest index is most significant
 Ḅ when they're converted from binary.
 Ṭ Generate the shortest array of 1s and 0s that has 1s at exactly those indices,
 P and check that it doesn't contain any 0s.

Since there's no leading 1, this identifies every non-leaf node with its leftmost descendant, but this seems not to matter.

Answer 2

Wolfram Language (Mathematica), 55 bytes

-6 bytes thanks to @att.

Length[l=If[0>##,0,#+2#0@##2]&@@@#~Position~_List]l&

Try it online!

• att: 57
• att: 55 (\[VectorGreaterEqual] -> \[VectorGreater])

Answer 3

05AB1E, (削除) 37 (削除ここまで) 34 bytes

×ばつ€"Dÿƶ ̃s"J.V\)ø<í2δβ>{āQ

Port of @UnrelatedString's Jelly answer, but unfortunately 05AB1E lacks a multi-dimensional indices builtin, so we'll have to do that manually at the cost of 26 bytes.. :/

Uses 1 as leaves.

Try it online or verify all test cases.

Explanation:

Δ€`}\N # Determine the depth-1 of the (implicit) multi-dimensional input-list:
Δ # Loop until the result no longer changes:
 €` # Flatten it one level down
 }\ # After the loop: discard the resulting flattened list
 N # And push the last (0-based) index of the loop instead
Ý # Pop and push a list in the range [0,depth-1]
 ×ばつ # Map each to that many "€" as string
 € # Then map each string to:
 "Dÿƶ ̃s" # String "Dÿƶ ̃s", where `ÿ` is replaced with the "€"-string
 J # Join this list of strings together
.V # Evaluate and execute it as 05AB1E code:
 D # Duplicate the multi-dimensional list of 1s
 € # Zero or more `€`: map to a certain depth:
 ƶ # Multiply each value by its 1-based index
 ̃ # Flatten the multi-dimensional list
 s # Swap, so the multi-dimensional list of 1s is at the top again
 \ # Discard the last multi-dimensional list of 1s
 ) # Wrap all flattened lists on the stack into a list
 ø # Zip/transpose; swapping rows/columns
 < # Decrease everything from 1-based to 0-based indices
í # Reverse each inner list of multi-dimensional indices
 δ # Map over each list:
 2 β # Convert it from a base-2 list to an integer
 > # Increase each 0-based value by 1 to a 1-based value
 { # Sort it
 ā # Push a list in the range [1,length] (without popping the list)
 Q # Check if the two lists are the same, in which case there are no gaps
 # (which is output implicitly as result)

Determining the depth of a ragged-list (Δ€`}\N) I've done before in this challenge.
Determining the multi-dimensional indices of a ragged-list (×ばつ€"Dÿƶ ̃s"J.V\)ø<) I've done before in this challenge.

Answer 4

Charcoal, 23 bytes

FNo⭆1θ1⊞υ∨¬ιE2§υ⊘−ικ=θ⊟υ

Try it online! Link is to verbose version of code. Takes input as a list using 1 for leaves (note that Charcoal takes a list of inputs, so there's an extra set of []s) and outputs a Charcoal boolean, i.e. - for contiguous, nothing if not. Explanation: Port of my Retina 0.8.2 answer.

FNo⭆1θ1

Count the number of leaves.

⊞υ∨¬ιE2§υ⊘−ικ

Generate the balanced tree with that number of leaves.

=θ⊟υ

Compare it to the input.

Answer 5

JavaScript (ES6), 69 bytes

Expects a nested list of 1's. Returns a Boolean value.

a=>!((m=F=(a,v,q)=>+a||a.map(b=>F(b,v+=q,q*2),m|=1<<v))(a,1,1),m&m+2)

Try it online!

Commented

a => !( // a[] = input array
 ( m = // m = bit mask to store node indices
 F = ( // F is a recursive function taking:
 a, // a[] = current node
 v, // v = node index
 q // q = highest power of 2 such that q ≤ v
 ) => //
 +a || // stop if this is a leaf
 a.map(b => // otherwise, for each child node b[]:
 F( // do a recursive call:
 b, // pass the child node
 v += q, // add q to v
 q * 2 // double q
 ), // end of recursive call
 m |= // update the bit mask m ...
 1 << v // ... so that the current node index is marked
 ) // end of map()
 )(a, 1, 1), // initial call to F with a[] = input and v = q = 1
 m & m + 2 // test whether m has any bit in common with m + 2
) // (if not, the only 0 in m is the trailing 0)

Answer 6

Retina 0.8.2, 48 bytes

$
¶$`
T`[,]`_`^.+
+`(L+)(1円L?)
[2,ドル1ドル]
^(.+)¶1円$

Try it online! Link includes test cases. Explanation: Pretty sure this works, but I don't know how to prove it.

$
¶$`

Duplicate the input.

T`[,]`_`^.+

Flatten one copy.

+`(L+)(1円L?)
[2,ドル1ドル]

Turn into a balanced tree.

^(.+)¶1円$

Check whether this equals the original tree.

Answer 7

Haskell, 53 bytes

data T=T T T|L
h L=[0]
h(T l r)=[1+d|d<-h l,h r==[d]]

Try it online!

• xnor: What are the truthy/falsey outputs you're using?
• Roman Czyborra: (>[]) is truthy.

Answer 8

Python3, 232 bytes:

def b(x,c,r,d):
 if isinstance(x,list):d[c]=d.get(c,[])+[r];b(x[0],c+1,'10'+r[1:],d);b(x[1],c+1,'11'+r[1:],d)
def f(t):d={};b(t,0,'1',d);K=sorted([int(i,2)for j in d for i in d[j]]);return all(K[j]+1==K[j+1]for j in range(len(K)-1))

Try it online!

Answer 9

julia, 47 bytes

Expects a nested list of 0s.

Truthy output: true or a positive integer of the total number of leaves

Falsy output: a negative integer

c(t)=t==0||(0<=-(c.(t)...)<2)*(+(c.(t)...,1))-1

The criterion is that a tree is truthy if, for each neighbouring pair of subtrees \$T_1, T_2\$ with the same parent node, the number of leaves in \$T_1\$ must be equal to or exactly one more then the number of leaves in \$T_2\$

The function c returns true on a leaf. Otherwise, we compute recursively -(c.(t)...) (which is equivalent to c(t[1]) - c(t[2])). This will be either 0 or 1 if t is truthy or sometimes if both t[1] and t[2] are falsy.

In any case, if the condition holds, we return +(c.(t)...,1)-1 (equivalent to c(t[1]) + c(t[2])), which is the total number of leaves if t is truthy and negative otherwise. If the condition fails, we return -1.

Attempt This Online!