ppc_90

Dark Forest (PPC, 90p)

Description: Someone pre-ordered a forest and now I'm lost in it. 
There are a lot of binary trees in front and behind of me. 
Some are smaller or equal-sized than others. 
Can you help me to invert the path and find out of the forest? 
Hint: It's about (inverted) BSTs. Don't forget the spaces. 

###ENG PL

Server sends input as:

I'm lost in a forest. Can you invert the path?
Level 1.: [13, 3]

This is list of binary tree nodes in pre-order. Our task is to recontruct the tree, invert it and send to the server as pre-order. Inverting the tree means that any left branch becomes right branch, and right branch becomes left:

def invert_tree(root):
    left = root.left
    right = root.right
    root.right = left
    root.left = right
    if root.right is not None:
        invert_tree(root.right)
    if root.left is not None:
        invert_tree(root.left)

Traversing and printing pre-order means that we print the value of the node before we print the branches nodes:

def display(root):
    result = []
    result.append(root.data)
    if root.left is not None:
        result.extend(display(root.left))
    if root.right is not None:
        result.extend(display(root.right))
    return result

Therefore we simply read nodes from input, add them to the tree, invert it and send inverted tree as response. Complete solution is here.

After 100 tasks we get the flag: IW{10000101010101TR33}

###PL version

Serwer przysyła dane jako:

I'm lost in a forest. Can you invert the path?
Level 1.: [13, 3]

To jest lista węzłów drzewa binarnego w porządku pre-order. Naszym zadaniem jest odbudować drzewo, odwrócić je a następnie wysłać je do serwera w porządku pre-order. Odwracanie drzewa oznacza że każda lewa gałąź staje się prawą a prawa lewą:

def invert_tree(root):
    left = root.left
    right = root.right
    root.right = left
    root.left = right
    if root.right is not None:
        invert_tree(root.right)
    if root.left is not None:
        invert_tree(root.left)

Przechodzenie i wypisanie drzewa pre-order oznacza że najpierw wypisujemy wartość danego węzła a dopiero potem jego gałęzi:

def display(root):
    result = []
    result.append(root.data)
    if root.left is not None:
        result.extend(display(root.left))
    if root.right is not None:
        result.extend(display(root.right))
    return result

W związku z tym pobieramy z wejścia listę węzłów, dodajemy je do drzewa, odwracamy je i odsyłamy odwrócone drzewo jako odpowiedź. Całe rozwiązanie jest tutaj.

Po 100 przykładach dostajemy flagę: IW{10000101010101TR33}