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]]
4
has two more brackets around it than the3
, but is diagramed only 1 layer deeper. \$\endgroup\$