Challenge: Level by Level

Lab Python Intermediate 20 points

Print the tree level by level: one line per level, values from left to right separated by spaces. Use a queue.

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

One line per level.

Example

Input

1 2 3 4 5 N 6

Output

1
2 3
4 5 6

Sample input available Sample output available

Editor

Python

Hints

Start the queue with the root.

At the start of each round, len(q) is the size of the current level.

Solution explanation

Breadth-first search visits nodes in order of their distance from the root.

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())

q = deque([root])
while q:
    row = []
    for _ in range(len(q)):
        node = q.popleft()
        row.append(str(node.value))
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)
    print(" ".join(row))

Output

Answer