11
\$\begingroup\$

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

9 Answers 9

11
\$\begingroup\$

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.

\$\endgroup\$
0
6
\$\begingroup\$

Wolfram Language (Mathematica), 55 bytes

-6 bytes thanks to @att.

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

Try it online!

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

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.

\$\endgroup\$
5
\$\begingroup\$

Charcoal, 23 bytes

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

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.

F№⭆¹θ1

Count the number of leaves.

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

Generate the balanced tree with that number of leaves.

⁼θ⊟υ

Compare it to the input.

\$\endgroup\$
5
\$\begingroup\$

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)
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

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!

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

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!

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.