Challenge: Three Traversals

Lab Python Beginner 10 points

Print the preorder, inorder and postorder traversals of the tree, each on its own line, values separated by spaces.

Input

One line: the tree in level order (row by row, left to right), with N for a missing child. For example 1 2 3 N 4 is 1 with children 2 and 3, and 2 has only a right child 4. The starter code already builds the tree for you.

Output

Three lines: preorder, inorder, postorder.

Example

Input

1 2 3 4 5

Output

1 2 4 5 3
4 2 5 1 3
4 5 2 3 1

Sample input available Sample output available

Editor

Python

Hints

Preorder: node, left, right.

Inorder: left, node, right.

Postorder: left, right, node.

Solution explanation

The three orders use the same recursion; only the position of the current node changes.

Show solution

from collections import deque


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def build(tokens):
    """Build a tree from level-order values; "N" means no node."""
    if not tokens or tokens[0] == "N":
        return None
    root = Node(int(tokens[0]))
    q = deque([root])
    i = 1
    while q and i < len(tokens):
        node = q.popleft()
        if tokens[i] != "N":
            node.left = Node(int(tokens[i]))
            q.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != "N":
            node.right = Node(int(tokens[i]))
            q.append(node.right)
        i += 1
    return root


root = build(input().split())


def pre(n):
    return [] if n is None else [n.value] + pre(n.left) + pre(n.right)


def ino(n):
    return [] if n is None else ino(n.left) + [n.value] + ino(n.right)


def post(n):
    return [] if n is None else post(n.left) + post(n.right) + [n.value]


for order in (pre, ino, post):
    print(" ".join(map(str, order(root))))

Output

Answer