/ app

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

Question

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

Solution

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

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

Example

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 visit(node) 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 breadth_first_traversal(root)