Fix your trees!

Question

In informatics, we often use trees in lots of different forms and representations. The three major methods of serialising binary trees are prefix, infix and postfix notation. For example, the following binary tree:

  _{(source: Dutch Olympiad in Informatics, finals, 2012/13)}

can be represented in prefix notation as abrxdbe, in infix as rbxabde and in postfix as rxbbeda.

In this case, you are confronted with a complete binary tree represented in infix notation. Your task is to convert this tree to prefix notation. Your input on stdin will be 2ⁿ-1 lowercase alphabet characters, a-z and no more, ended with a newline character, for any integer n such that 1 ≤ n ≤ 16. Thus, the maximum number of characters you will get is 65535. Output the tree to stdout in the same way, but then in prefix format.

This is code golf, so the shortest code, counted in bytes, will win. Votes will act as a tie breaker, and if those tie up as well, submission date and time.

Answer 1

GolfScript, 23 chars

.,\{;).2base{)!}do}$/n-

This solution uses a different approach than Howard's: basically, it sorts the input characters according to the list of branches needed to reach that character from the root of the tree.

Note that the newline at the end of the input is required (i.e. the input length must be a power of two). The n- at the end of the code is required to suppress an extra newline at the beginning of the output; if such a newline is acceptable, those characters can be omitted for a score of 21 chars.

As usual, you can test this code online.

Explanation:

• .,\ calculates the length of the input, and moves it below the input string on the stack. It will be used as the starting value of the loop counter used to construct the sort keys below. (The code relies on this being a power of two; otherwise the bit manipulation below will not produce the expected results. Any sufficiently large power of two would work, though.)

• { }$ sorts the characters in the input string according to the sort key computed inside the block:

  • ; just throws away the character given as input to the block; we don't care about the actual character values here, just about their positions within the string.

  • ). increments the loop counter on the stack (which was initialized to the length of the input string) and makes a copy of it.

  • 2base converts this copy to an array of bits (omitting leading zeros; that's why we need to start counting from a large enough power of two, rather than simply from zero).

  • {)!}do repeatedly chops off the lowest bit from the array until the chopped-off bit is a 1.

  Since the resulting sort keys are arrays, the $ compares them lexicographically. Thus, for example, the array [1] (which corresponds to the root node) sorts before [1 0] (which corresponds to the left child of the root node) and [1 1] (the right child of the root node).

• At the end, / gets rid of the loop counter by using it as the length of chunks to split the output string into (thanks, Peter!), and n- strips the newline off the sorted input string. (The GolfScript interpreter will append another newline to the output after printing the contents of the stack.)

Answer 2

GolfScript, 28 characters

{.,1>{.,)2//([)\c]\~c+}*}:c~

You may test the code online.

Annotated code:

# define an operator c acting on the top of stack which does the conversion
{
  # if the input string is more than a single character
  .,1>{
    # split string into two halves (rounded up)
    .,)2//   
    # take first part last character
    ([)
    # take first part rest and call c recursively
    \c]
    # get second part
    \~
    # call c recursively on second part
    c
    # join all three together 
    +
  }*
}:c
# call c
~       

Answer 3

GolfScript (29 chars)

{.,1>{.,)2//~\[)](f@f++}*}:f~

Online demo

Works with or without the trailing newline in input.

Answer 4

APL (48)

(Yes, the APL charset does fit in a byte.)

{1=⍴⍵:⍵⋄(⊃a),⊃,/∇¨1↓a←1⌽⌽⍵⊂⍨(⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵}⍞

Explanation:

• {...}⍞: read input, feed to function
• 1=⍴⍵:⍵: if the input length is one, we're done
• ⋄: otherwise:
• (⍳⍴⍵)∊1,0 1+⌈.5×⍴⍵: make a bitfield of places to split the input (first character, middle character and character past the middle character)
• ⍵⊂⍨: split the input at these places
• a←1⌽⌽: rotate the sub-arrays so that the middle character is first, the left hand is second and the right hand is third, and store in a.
• ⊃,/∇¨1↓a: run the function again on the last two elements of a and concatenate the results
• (⊃a),: and concatenate that to the first item in a

Answer 5

Python 3 - 76

def f(x):a=len(x)//2;return x and x[a]+f(x[:a])+f(x[a+1:])
print(f(input()))

Answer 6

C, 108 chars

My code uses a recursive function, which always prints the character in the middle of the buffer, and calls itself with the part of the string before and the part of the string after the character printed. (Divide and Conquer)

char b[65536];d(s,e){int c=s+(e-s)/2;putchar(b[c]);if(c^s)d(s,c-1),d(c+1,e);}main(){gets(b);d(0,strlen(b));}

ungolfed:

char b[65536];
d(s,e){
    int c=s+(e-s)/2;
    putchar(b[c]);
    if(c^s)d(s,c-1),d(c+1,e);
}
main(){
    gets(b);
    d(0,strlen(b));
}