Turn over a new leaf

Question

You're given a tree, which in computer science tradition, has the root at the top and leaves at the bottom. The leaf nodes are labelled with numbers. Your goal is to take the special leaf marked -1 and move it up to be the new root.

[3, [[16], -1], [4]] --> [[[[4], 3], [16]]]

You can imagine rotating the special leaf to the top and letting the rest of tree hang off of it. Keeping the tree in the plane while rotating it to get the correct left-to-right order of all the branches.

The new tree has all the leaves of the original tree except for -1.

Input:

A tree whose leaves are distinct positive integers, except for one leaf of -1. The root of the tree will have at least two branches coming off.

The input is given as a nested list like [3, [[16], -1], [[4]]] or its string representation. Delimiters are optional and up to you, but adjacent numbers need to be separated.

Output:

Output or print the flipped tree in the same format as your input. The order of the list entries must be correct. In-place modification is fine.

If your input/output is a data type, it must be one that prints in the required format by default. Built-ins that basically do the task for you are not allowed.

Test cases:

>> [3, [[16], -1], [4]]
[[[[4], 3], [16]]]

>> [2, -1]
[[2]]

>> [44, -1, 12]
[[12, 44]]

>> [[[[-1]]], [[[[4]]]]]
[[[[[[[[[4]]]]]]]]]

>> [[1, 2, 3], [4, -1, 6], [7, 8, 9]]
[[6, [[7, 8, 9], [1, 2, 3]], 4]]

>> [9, [8, [7, [6, -1, 4], 3], 2], 1]
[[4, [3, [2, [1, 9], 8], 7], 6]]

Answer 1

CJam, 24 24 22 bytes

l~{):T]{s$}$(+T1+}gW<p

Try it online.

Thanks Dennis for removing 2 bytes.

Explanation

l~          e# Read the input.
{           e# Do:
    ):T     e# Save the last item to T.
    ]       e# Wrap everything else (as an array) and the last item into an array,
    {s$}$   e#   where the one with -1 (having "-" if stringified) is the first item.
    (+      e# Insert the second array into the first array as the first item,
            e#   or just move the -1 to the end if the first item is already -1.
    T1+     e# Check if the array before this iteration ended with -1.
}g          e# Continue the loop if it did't.
W<p         e# Remove the -1 and print.

Answer 2

Pyth, 26 25 24 23 bytes

L?y.>b1}\-`Jtb.xyahbJ]J

Demonstration. Test Harness.

This defines a function, y, which takes a nested Pyth list as input.

There are three cases to explore in this recursive function, due to the ternary, ?, and the try - except function, .x. In the function, the input is b.

The first case occurs when }\-`Jtb is truthy. This tests whether there is a - in the string representation of tb, the "tail" of b, which is all of b except its first element. tb is also stored in J. Since all labels are positive except for -1, this will be true if and only if the -1 is not in the first element of the list.

In this case, we cyclically right shift b by 1 with .>b1, and then call the function recursively. This ensures that we will progress to the next step with the element containing -1 as the head (first element) of the list.

In the next two cases, the above is falsy, so -1 is in the head of the list.

In the second case, ahbJ does not throw an error. An error will be thrown if and only if hb is an integer. If this is not the case, then hb is a list, and we need to rotate the tree so that the -1 leaf is nearer the root. ahbJ accomplishes this by appending J as a single element at the end of hb, which effectively moves the root of the tree from b to hb.

In the third and final case, an error is thrown. Thus, hb is a single element. Because of the test in the first case, hb must be -1. Thus, we can return the rest of b, namely J, wrapped in a list, namely ]J.