15
\$\begingroup\$

Task

Given a list of nodes representing a binary tree of positive integers serialized depth-first, return a list of nodes representing the same tree serialized breadth-first. To represent an absent child, you may use null, 0, 'X', Nothing, [], or any other value that is distinct from your representation of a node's value, which can be represented by an integer or an integer in a singleton list or other collection.

For example, here is an example tree :

         1
      /     \
     /       \
    5         3
   / \       / \
  #   4     10  2
     / \   / \ / \
    4   6 #  # #  7
   /\  /\         /\
  # # #  #       #  #

Serialized depth-first, this would be [1, 5, #, 4, 4, #, #, 6, #, #, 3, 10, #, #, 2, #, 7, #, #] (here, # indicates that a child does not exist). This list was made using a pre-order traversal (add a node's value to the list, serialize its left child or add # if it doesn't exist, serialize its right child or add # if it doesn't exist).

Serialized breadth-first, this would be [1, 5, 3, #, 4, 10, 2, 4, 6, #, #, #, 7, #, #, #, #, #, #] (you may trim as many of the #'s at the end as you want, I just wanted to make them explicit). Here, you write the root node's value, then the values of all the nodes on the level below, left to right (with a # where a node doesn't exist), then values of the level below, until all the nodes are added to the list.

Test cases

[1] -> [1, #, #] //or [1], whatever you wish

Tree: 1   //or just 1
     / \
    #   #
([1, #, #] and [1, #] yield the same result as above)

[100, 4, 5, #, #, #, #] -> [100, 4, #, 5, #, #, #]
Tree:    100
        /   \
       4     #
      / \
     5   #
    / \
   #   #

[10, 5, 2, 2, #, #, 2, #, #, #, 4, 8, 4, #, #, #, 1, #, #] -> [10, 5, 4, 2, #, 8, 1, 2, 2, 4, #, #, #, #, #, #, #, #, #]
Tree:     10
        /    \
       5      4
      / \    / \
     2   #  8   1
    / \    / \  / \
   2   2  4  # #  #
  /\  /\  /\
 # # # # # #

[100, #, 4, 5, #, #, #] -> [100, #, 4, 5, #, #, #]
Tree:    100
        /   \
       #     4
            / \
           5   #
          / \
         #   #

This is , so shortest code wins!

Brownie points for coming up with a better name for this question

\$\endgroup\$
2
  • 2
    \$\begingroup\$ shouldn't your second test case be [100, 4, 5, #, #, #, #] instead of [100, 4, 5, #, #, #]? \$\endgroup\$
    – Jakque
    Jun 17 at 8:28
  • 1
    \$\begingroup\$ @Jakque Yes, it should, sorry for all the errors. \$\endgroup\$
    – user
    Jun 17 at 18:20
4
\$\begingroup\$

JavaScript (ES10),  90 80  78 bytes

Uses undefined for an absent child.

a=>(g=d=>(b[d]=b[d]||[]).push(x=a[p++])*x&&[++d,d].map(g))(p=0,b=[])&&b.flat()

Try it online!

Commented

We recursively walk through the input array a[], using the depth-first way. While doing so, we fill the array b[] where the values are organized by depth. At the end of the process, we just need to flatten b[] to get the final output.

a =>                  // a[] = depth-first input
( g = d =>            // g is a recursive function taking a depth d
  (b[d] = b[d] || []) //   create b[d] if it doesn't exist
  .push(              //   and push the value ...
    x = a[p++]        //   ... stored in a[] at position p; increment p afterwards
  )                   //
  * x &&              //   if this value is defined:
    [++d, d].map(g)   //     do two recursive calls to g with d + 1
)(                    // initial call to g with:
  p = 0,              //   d = p = 0
  b = []              //   b[] initialized to an empty array
)                     //
&& b.flat()           // end of call: return a flattened version of b[]
\$\endgroup\$
4
\$\begingroup\$

Haskell, 88 bytes

(concat=<<).foldr(#)[]
0#a=[[0]]:a
x#(p:q:a)=([x]:p%q):a
(u:p)%(v:q)=(u++v):p%q
p%q=p++q

Try it online!

also 88 bytes

(concat=<<).foldr(#)[]
0#a=[[0]]:a
x#(p:q:a)=([x]:zipWith(++)(p++([]<$q))(q++([]<$p))):a

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 194 bytes

def f(x):
	c=x[:1]+[0]*3
	for k in x[1:]:
		p=-(k<1)or[k,0,0,c];c[1+(c[1]!=0)]=p
		if k:c=p
		while k<all(c[2:4]):c=c[3]
	while c[3]:c=c[3]
	q=[c]
	for x in q:
		if-1!=x:x,*w,_=x;q+=w
		print(x)

Try it online!

-24 bytes thanks to Jakque
-35 bytes thanks to ovs

Very bad solution, but it implements the task directly and shouldn't be extremely inefficient at least. It basically deserializes iteratively by just taking each element and storing a current list maintaining [value, left-child, right-child, parent] (since Python handles recursive lists perfectly fine), and then re-serializes using a trivial queue method.

Commented and ungolfed version:

def f(x):                                            # Accept a list with null values as 0

	c = [x[0], 0, 0, 0]                          # Maintain current list [value, left child, right child, parent], starting at the root

	for k in x[1:]:                              # For each element after the first
		p = k and [k, 0, 0, c] or -1         # p is the child - if the value is null, -1, otherwise, another 4-list of the right format
		a = c[1] != 0                        # a is true if and only if the left child is already taken
		c[1] = [p, c[1]][a]                  # if the left child isn't taken, set the left child, otherwise, leave it
		c[2] = [c[2], p][a]                  # if the left child is taken, set the right child, otherwise, leave it

		if k < 1:                            # if this is a null value
			while c[3] and c[2] != 0:    # so long as both children are full
				c = c[3]             # step back up once

		else:                                # if this isn't a null value
			c = c[1 + a]                 # descend to the new child

	while c[3]:                                  # as long as this isn't the root
		c = c[3]                             # step up (this just goes to the root)

	q = [c]                                      # start a queue with just the root
	for x in q:                                  # keep going through the queue
		print(x == -1 and -1 or x[0])        # if the current value is -1, output it, otherwise, you get a 4-list, and output the value from it
		q += x != -1 and x[1:3] or []        # if the current value is -1, nothing, otherwise, add the left and right children to the queue

Try it online!

\$\endgroup\$
7
  • 1
    \$\begingroup\$ if k<1:<code1> else:<code2> can be shortened as if k:<code2> else:<code1> for -2 bytes. x==-1and-1 => -(x==-1) saves 2 more bytes. while c[3]and c[2]!=0: => while c[3]and c[2]: => while all(c[2:4]): saves 4 bytes \$\endgroup\$
    – Jakque
    Jun 17 at 14:34
  • 1
    \$\begingroup\$ I just found a -7 bytes ^^ : else:while all(c[2:4]):c=c[3] =>while k<all(c[2:4]):c=c[3]. The condition will always be false if k>0 wich saves the else \$\endgroup\$
    – Jakque
    Jun 17 at 14:56
  • 1
    \$\begingroup\$ ok last more thing : c[1]=[p,c[1]][a];c[2]=[c[2],p][a]=>c[1],c[2]=[p,c[1],c[2],p][a::2] => c[1:3]=[p,*c[1:3],p][a::2] saves 7 more bytes \$\endgroup\$
    – Jakque
    Jun 17 at 15:31
  • 2
    \$\begingroup\$ 196 bytes, the biggest save is c[1:3]=[p,*c[1:3],p][a::2] -> c[1+a]=p. \$\endgroup\$
    – ovs
    Jun 17 at 18:57
  • 1
    \$\begingroup\$ 194 : a=c[1]!=0;c[1+a]=p +> c[1+(c[1]!=0)]=p \$\endgroup\$
    – Jakque
    Jun 17 at 22:05
4
\$\begingroup\$

Python 3, 126 110 84 bytes

def f(a,d=0,L=[]):L+=[[]];L[d]+=a[:1];a.pop(0)and f(a,d+1)+f(a,d+1);return sum(L,[])

Try it online!

How it works:

The main idea is to reconstruct the layers of the graph in L. To do that, we will be doing some recursion and store the current depth in d.

Ungolfed and commented version:

def f(a, d=0, L=[]): # a is our array, d is the currend depth, L are the layers
    L += [[]]          # append an empty layer in L to avoid future IndexError
    L[d] += a[:1]      # add the root of our current tree in the right layer

    if a.pop(0) != 0:  # Remove the first element of our tree and check if it is a root of a sub tree
        f(a, d+1) +      # compute the first sub-tree (append the nodes to the layers and remove them)
        f(a, d+1)        # compute the second sub-tree (same)
      
    return sum(L,[])   # return the flatened list of the layers

Note:

As the program use the variable L as a reference, re-use the function after its first call will not return the good result because L won't have been reinitialized.

edit : In my previous answer, I cared a lot about the length of the sub-trees to recurse a at the right indice but it is no longer the case since we discard the elements of a when we visit them. The consequence of that is that a is empty at the end of the function, but who cares in a golf challenge ¯\_(ツ)_/¯

\$\endgroup\$
4
\$\begingroup\$

R, 118 114 113 bytes

f=function(x,d=1,G=new.env()){G$g=c(G$g,d)
o=x[-1]
if(sum(o|1)&x)o=f(f(o,d+1,G),d+1,G)
`if`(d<2,x[order(G$g)],o)}

Try it online!

The idea

Traverse the array by reviving the DFS and keeping track of the visited recursion depths; then use the depths to order the array BFS-wise.

Unrolled code and explanation:

f=function(       # function args:
     x,           #  - vector x
     d=1,         #  - current recursion depth d (default=1)
     G=new.env()  #  - a passed-by-reference obj (enviroment)
     ){
  G$g=c(G$g,d)    # concat curr.depth to vector of depths
                  # (the vector is a var. inside the enviroment, initially NULL)
  o=x[-1]         # remove first element of x storing the result in o
  if(sum(o|1)&x){ # if o has elements and the first element of x > 0
    o=f(o,d+1,G)  #  recurse on left branch increasing d and updating o
    o=f(o,d+1,G)  #  recurse on right branch increasing d and updating o
  }
  if(d<2){        # if d == 1
    x[order(G$g)] #  use the stored depths to reorder x and return it
  }else{          # else
    o             #  return o
  } 
}
\$\endgroup\$
3
\$\begingroup\$

Jelly, 28 bytes

Ḣ;ß},ß}ɗ¥WAƑ?
J×ṠÇAœiⱮJẈż$Ụị

Try it online!

Uses -1 for an absent child. This recreates a binary tree of the list indices and then sorts the original list based on the depth and position of the indices.

Explanation

Helper link

Takes a list of integers representing a depth-first binary tree and recursively turns it into a representation of that tree using nested lists

Ḣ             | Head
          AƑ? | If non-negative:
        ¥     | - Then:
 ;            |   - Concatenate to:
  ß},ß}ɗ      |   - The results of calling this link recursively using the remainder of the list, pairing the results of each call together
         W    | - Else: wrap in a list

Main link

J              | Sequence along list
 ×Ṡ            | Multiplied by the signs of the original list
   Ç           | Call helper link
    A          | Absolute
     œiⱮJ      | Find multi-dimensional indices of each list index
         Ẉż$   | Prepend the list lengths (i.e. depth)
            Ụ  | Indices required for this sort order
             ị | Index into original list
\$\endgroup\$
3
\$\begingroup\$

R, 80 bytes

for(i in x<-scan()){F=c(F,T);T=T+(i>0)*T+!i;while(!T%%2+i)T=T/2};x[order(F[-1])]

Try it online!

Full program, takes leaf nodes as \$0\$. Runs through the input and keeps track of the current depth in the following way:

  • Store the current value of depth accumulator T (preinitialized to \$1\$) in F.
  • If the current node is positive, move to the next level (multiply T by 2).
  • Otherwise increase T by 1. If after this addition, T is divisible by 2, we've already had two child nodes in this level, and need to keep backing up (divide T by 2) until it is no longer divisible.

In other words, we can imagine T as a binary number, where each bit represents a level, \$0\$ is its first branch, and \$1\$ is its second branch. Moving to a new level is equivalent to adding another zero bit, and when the number "wraps around" all trailing zeroes are removed. For example, in the demo input:

[1, 5, #, 4, 4, #, #, 6, #, #, 3, ...]

Input     Next depth     
          1
1     ->  10
5     ->  100
0     ->  101
4     ->  1010
4     ->  10100
0     ->  10101
0     ->  1011
6     ->  10110
0     ->  10111
0     ->  11    
3     ->  110
...

Finally, return x sorted in the order of F.

\$\endgroup\$
1
  • \$\begingroup\$ This is awesome! \$\endgroup\$
    – digEmAll
    Jun 21 at 6:15
1
\$\begingroup\$

Stax, 31 bytes

ü§!■YΦ─Ä↓Θ½(-²9♂^♀_¡#{Σ├j↨à,lqƒ

Run and debug it

null nodes are represented by 0, and are required in the input in all places applicable.

parses the given traversal into a nested list, and then flattens it into layers. The parsing part is actually much smaller than the portion which prints the layers, somehow.

Golfed a bit with some help from recursive.

Explanation

Gd{c{|4!fsn|-:f:fcwLr$J}Bsn!CGG~2l]+,
| printing             || parsing   |

Bsn!CGG~2l]+,
B               remove first element and push
 sn!C           if zero, stop recursion
    GG          do 2 recursive calls
      ~         move array to input stack
        2l]+    create a pair from the recursive calls, prepend previous iteration
            ,   retrieve array from input stack

Gd{c{|4!fsn|-:f:fcwLr$J}
G                      } run after recursive operation is over
 d                       delete empty list
  {              cw      run as long as tree isn't empty
   c{|4!f                copy, get elements at depth 0
         sn|-            remove those from the original tree
             :f:f        flatten twice
                   Lr    put all levels in a list
                     $   flatten
                      J  join with spaces
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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