Interview Practice 16 – Print Binary Tree Layer-by-layer


Print a binary tree layer-by-layer from top to bottom, and from left to right for each layer.


Yes, it’s a simple task. We can use breadth-first search, and which means we need a queue, see reference.

    q = empty queue
    while not q.empty do
        node := q.dequeue()
        if node.left ≠ null then
        if node.right ≠ null then


# node structure
class bst_node:
    value = None
    left = None
    right = None
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

# what to do with a node.
def visit(node):
    print node.value,

# bfs traversal
def breadth_first_traversal(root):
    queue = [root]
    while len(queue) > 0:
        node = queue.pop(0) # get the head item
        if node.left: queue.append(node.left)
        if node.right: queue.append(node.right)

# a binary tree and display how was it before reflection
node_05 = bst_node(5)
node_07 = bst_node(7)
node_09 = bst_node(9)
node_11 = bst_node(11)
node_06 = bst_node(6,  node_05, node_07)
node_10 = bst_node(10, node_09, node_11)
node_08 = bst_node(8,  node_06, node_10)

# answer should be: 8 6 10 5 7 9 11
root = node_08

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: