Print a tree one level at a time, from the top down.
What to build
A breadth-first walk of a tree, using a queue.
Requirements
- Build the search tree by inserting the numbers in the given order.
- Print each level on one line, from left to right, with values separated by spaces.
Input
The first line has n. The second line has n different whole numbers.
Output
One line per level.
Constraints
n is from 1 to 200.
Example
Input:
4
5 3 8 1
Output:
5
3 8
1
Why it works
A queue serves nodes in the order they were found, so all of one level is finished before the next begins. Counting a level's nodes first keeps the lines separate.
Examples
Example 1 · Input
4 5 3 8 1
Expected output
5 3 8 1
Example 2 · Input
1 9
Expected output
9
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Use a deque holding the nodes of the current level.
Hint 2
len(queue) at the start of a round tells you how many nodes that level has.
Hint 3
Add each node's children to the back of the queue.
Solution
Show one correct solution (try it yourself first)
from collections import deque
class Tree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return Tree(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
n = int(input())
root = None
for v in input().split():
root = insert(root, int(v))
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
level.append(str(node.value))
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
print(" ".join(level))