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:

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

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!

Answer 3

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.

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

Answer 4

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.

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+)(\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.

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!

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!