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

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.

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]]]

• Assuming solutions have to handle unbalanced trees, it would help to have one in the falsy test cases. May 5, 2023 at 1:24
• @alephalpha Nodes are branches; leaves don't count as nodes. May 5, 2023 at 2:14
• 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. May 8, 2023 at 20:21
• @DavidG. Nodes are branches; leaves don't count as nodes. May 8, 2023 at 21:33
• @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. May 8, 2023 at 22:00

# Jelly, 111098 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.

# Wolfram Language (Mathematica), 55 bytes

-6 bytes thanks to @att.

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


Try it online!

• 57
– att
May 5, 2023 at 7:18
• 55 (\[VectorGreaterEqual] -> \[VectorGreater])
– att
May 5, 2023 at 7:22

# 05AB1E, 37 34 bytes

Δ€}\NÝ"€"×€"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.

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 (Δ€}\NÝ"€"×€"Dÿƶ˜s"J.V\)ø<) I've done before in this challenge.

# Charcoal, 23 bytes

Ｆ№⭆¹θ1⊞υ∨¬ιＥ²§υ⊘⁻ικ⁼θ⊟υ


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.

Ｆ№⭆¹θ1


Count the number of leaves.

⊞υ∨¬ιＥ²§υ⊘⁻ικ


Generate the balanced tree with that number of leaves.

⁼θ⊟υ


Compare it to the input.

# 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)


# Retina 0.8.2, 48 bytes

$¶$
T[,]_^.+
+(L+)(\1L?)
[$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+)(\1L?) [$2,$1]  Turn into a balanced tree. ^(.+)¶\1$


Check whether this equals the original tree.

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


Try it online!

• What are the truthy/falsey outputs you're using?
– xnor
May 8, 2023 at 19:40
• (>[]) is truthy. May 9, 2023 at 18:52

# 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!

# 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!