Printing binary tree

Problem

Write a function to print the rows of a binary tree, terminating each row with a carriage return.

Answer

This question can be solved using the Breadth First Search.

Using std::list as a queue, we can print each node and print the carriage return when we change the level.

To do so, we need to remember the number of children at each level.

Overall running time will be $O ( N )$, where N is the number of nodes in the tree.

Here is the complete code.

	include <list>
	#include <iostream>
	using namespace std;
	struct node {
	node * left;
	node * right;
	int value;
	node(int v):value(v), left(0), right(0){}
	};
	void print_tree(node * root)
	{
	int n_child = 1;
	int next_child = 0;
	list<node*> queue;
	queue.push_back(root);
	while(queue.size())
	{
	node * cur = queue.front();
	queue.pop_front();
	if (cur->left)
	{
	queue.push_back(cur->left);
	next_child++;
	}
	if (cur->right)
	{
	queue.push_back(cur->right);
	next_child++;
	}
	n_child--;
	cout <<cur->value<<" ";
	if (n_child == 0)
	{
	cout<<endl;
	n_child = next_child;
	next_child=0;
	}
	}
	}
	int main()
	{
	node* n5 = new node(5);
	node* n2 = new node(2);
	node* n4 = new node(4);
	node* n6 = new node(6);
	n5->left= n2;
	n5->right = n4;
	n2->left = n6;
	print_tree(n5);
	return 1;
	}

view raw print_tree.cpp hosted with ❤ by GitHub

Practice statistics

08:46: to code up the solution

UPDATE (2019-07-18): solved the problem in python. using deque

	from collections import deque
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = None
	self.right = None
	def print_tree(root):
	if root == None:
	return
	q = deque()
	depth = 0
	q.append([root, depth])
	while q:
	current = q.popleft()
	if current[0] == None:
	continue
	if current[1] > depth:
	print('\n')
	depth = current[1]
	print(current[0].value),
	q.append([current[0].left, depth + 1])
	q.append([current[0].right, depth + 1])
	n0 = Node(0)
	n1 = Node(1)
	n2 = Node(2)
	n3 = Node(3)
	n4 = Node(4)
	n5 = Node(5)
	n6 = Node(6)
	n7 = Node(7)
	n0.left = n1
	n0.right = n2
	n1.left = n3
	n1.right = n4
	n2.left = n5
	n2.right = n6
	n3.left = n7
	print_tree(n0)

view raw print_binary_tree.py hosted with ❤ by GitHub

Practice statistics

25:00: to write code
5:00: to fix typo

UPDATE(2022-06-14): Solved again in python. This time I used just list and used pop(0) as a dequeue replacement. Had a bug in the code and took more than 9 mins to fix it.

	# code
	class Node:
	def __init__(self, value):
	self.value = value
	self.left = None
	self.right = None
	def print_bst(root):
	cur_count = 1
	queue = []
	next_count = 0
	queue.append(root)
	while len(queue) > 0:
	node = queue.pop(0)
	cur_count = cur_count - 1
	print("{} ".format(node.value), end='')
	if node.left != None:
	queue.append(node.left)
	next_count = next_count + 1
	if node.right != None:
	queue.append(node.right)
	next_count = next_count + 1
	if cur_count == 0:
	print ("")
	cur_count = next_count
	next_count = 0
	# test
	c9 = Node(9)
	c5 = Node(5)
	c11 = Node(11)
	c9.left = c5
	c9.right = c11
	c3 = Node(3)
	c6 = Node(6)
	c5.left = c3
	c5.right = c6
	c10 = Node(10)
	c12 = Node(12)
	c11.left = c10
	c11.right = c12
	c13 = Node(13)
	c12.right = c13
	print_bst(c9)

view raw print_bst.py hosted with ❤ by GitHub

9:30: coding

3:00: test code.