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\$ Commented May 5, 2023 at 1:24
  • 2
    \$\begingroup\$ @alephalpha Nodes are branches; leaves don't count as nodes. \$\endgroup\$ Commented 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\$ Commented May 8, 2023 at 20:21
  • \$\begingroup\$ @DavidG. Nodes are branches; leaves don't count as nodes. \$\endgroup\$ Commented 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\$ Commented 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\$ Commented May 5, 2023 at 7:18
  • 1
    \$\begingroup\$ 55 (\[VectorGreaterEqual] -> \[VectorGreater]) \$\endgroup\$ Commented 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\$ Commented May 8, 2023 at 19:40
  • \$\begingroup\$ (>[]) is truthy. \$\endgroup\$ Commented 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\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.