© Parineeth M R
Question 17. Print the nodes of a binary tree in level order
To print the nodes of the binary tree in level order, we start with the root node and then print the child nodes in each level from left to right. Consider the binary tree below
The level order printing will result in the following output: ABCDEFG. To achieve this we make use of a queue and use the following strategy:
1. Add the root node to the queue
2. Remove the head element of the queue and print it. Then add the children of the removed element back to the queue. Repeat step-2 till the queue becomes empty.
C/C++
/*
root: root node of the tree
q: queue that helps in printing in level order
*/
void print_level_order(struct node *root, queue<struct node*>& q)
{
struct node *n;
int num_nodes_in_cur_level, num_nodes_in_next_level;
if (!root)
return;
/*Add the root node to the empty queue*/
q.push(root);
num_nodes_in_cur_level = 1;
num_nodes_in_next_level = 0;
/*Process the nodes in the queue in Breadth First manner*/
while (!q.empty()) {
/*Remove the node at the head of the queue*/
n = q.front();
q.pop();
print_data(n->data); /*print the data in the node*/
/*Add the left child to the end of the queue*/
if (n->left) {
q.push(n->left);
num_nodes_in_next_level++;
}
/*Add the right child to the end of the queue*/
if (n->right) {
q.push(n->right);
num_nodes_in_next_level++;
}
num_nodes_in_cur_level--;
/*go to next line, if all nodes in current level are processed*/
if (num_nodes_in_cur_level == 0) {
cout << endl;
num_nodes_in_cur_level = num_nodes_in_next_level;
num_nodes_in_next_level = 0;
}
}
}
Java
/*
root: root node of the tree
q: queue used for printing the tree
*/
public static void printLevelOrder(TreeNode root, Queue<TreeNode> q) {
if (root == null)
return;
/*Add the root node to the empty queue*/
q.add(root);
int numNodesInCurLevel = 1;
int numNodesInNextLevel = 0;
/*Process the nodes in the queue in Breadth First manner*/
while (!q.isEmpty()) {
/*Remove the node at the head of the queue*/
TreeNode n = q.remove();
printData(n.data); /*print the data in the node*/
/*Add the left child to the queue*/
if (n.left != null) {
q.add(n.left);
numNodesInNextLevel++;
}
/*Add the right child to the queue*/
if (n.right != null) {
q.add(n.right);
numNodesInNextLevel++;
}
numNodesInCurLevel--;
/*go to next line, if all nodes in current level are processed*/
if (numNodesInCurLevel == 0) {
System.out.println();
numNodesInCurLevel = numNodesInNextLevel;
numNodesInNextLevel = 0;
}
}
}
Python
#root: root node of the tree
#q: Python Queue object used for printing the tree
@staticmethod
def print_level_order(root, q):
if (not root):
return
#Add the root node to the empty queue
q.put(root)
num_nodes_in_cur_level = 1
num_nodes_in_next_level = 0
#Process the nodes in the queue in Breadth First manner
while (not q.empty()) :
#Remove the node at the head of the queue
n = q.get()
TreeNode.print_data(n.data) #print the data in the node
#Add the left child to the queue
if (n.left) :
q.put(n.left)
num_nodes_in_next_level += 1
#Add the right child to the queue
if (n.right) :
q.put(n.right)
num_nodes_in_next_level += 1
num_nodes_in_cur_level = num_nodes_in_cur_level - 1
#go to next line, if all nodes in current level are processed
if (num_nodes_in_cur_level == 0) :
print('')
num_nodes_in_cur_level = num_nodes_in_next_level
num_nodes_in_next_level = 0
