{"id":27161,"date":"2018-01-03T21:56:57","date_gmt":"2018-01-03T16:26:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27161"},"modified":"2018-01-03T21:56:57","modified_gmt":"2018-01-03T16:26:57","slug":"print-level-order-traversal-line-line","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/print-level-order-traversal-line-line\/","title":{"rendered":"Print level order traversal line by line"},"content":{"rendered":"

Given a binary tree, print level order traversal in a way that nodes of all levels are printed in separate lines.<\/span><\/p>\n

For example consider the following tree<\/p>\n

          1\r\n       \/     \\\r\n      2       3\r\n    \/   \\       \\\r\n   4     5       6\r\n        \/  \\     \/\r\n       7    8   9\r\n\r\nOutput for above tree should be\r\n1\r\n2 3\r\n4 5 6\r\n7 8 9<\/pre>\n
\n
Recommended: Please solve it on “PRACTICE<\/u><\/i><\/b>” first,<\/h2>\n
before moving on to the solution.<\/h2>\n<\/div>\n
Note that this is different from simple level order traversal where we need to print all nodes together. Here we need to print nodes of different levels in different lines.<\/p>\n
A simple solution is to print use the recursive function discussed in the level order traversal post and print a new line after every call to printGivenLevel().<\/p>\n
\n
\n\n\n\n
\n
\n
\/* Function to line by line print level order traversal a tree*\/<\/code><\/div>\n
void<\/code> printLevelOrder(<\/code>struct<\/code> node* root)<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>int<\/code> h = height(root);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>int<\/code> i;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>for<\/code> (i=1; i<=h; i++)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>printGivenLevel(root, i);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>printf<\/code>(<\/code>\"\\n\"<\/code>);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>}<\/code><\/div>\n
}<\/code><\/div>\n
<\/div>\n
\/* Print nodes at a given level *\/<\/code><\/div>\n
void<\/code> printGivenLevel(<\/code>struct<\/code> node* root, <\/code>int<\/code> level)<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (root == NULL)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>return<\/code>;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (level == 1)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>printf<\/code>(<\/code>\"%d \"<\/code>, root->data);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>else<\/code> if<\/code> (level > 1)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>printGivenLevel(root->left, level-1);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>printGivenLevel(root->right, level-1);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>}<\/code><\/div>\n
}<\/code><\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n
The time complexity of the above solution is O(n2<\/sup>)<\/p>\n[ad type=”banner”]\n
How to modify the iterative level order traversal (Method 2 of this) to levels line by line?<\/strong>
\nThe idea is similar to this post. We count the nodes at current level. And for every node, we enqueue its children to queue.<\/p>\n
\n
\n\n\n\n
\n
\n
\/* Iterative program to print levels line by line *\/<\/code><\/div>\n
#include <iostream><\/code><\/div>\n
#include <queue><\/code><\/div>\n
using<\/code> namespace<\/code> std;<\/code><\/div>\n
<\/div>\n
\/\/ A Binary Tree Node<\/code><\/div>\n
struct<\/code> node<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>struct<\/code> node *left;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>int<\/code> data;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>struct<\/code> node *right;<\/code><\/div>\n
};<\/code><\/div>\n
<\/div>\n
\/\/ Iterative method to do level order traversal line by line<\/code><\/div>\n
void<\/code> printLevelOrder(node *root)<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ Base Case<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (root == NULL)\u00a0 <\/code>return<\/code>;<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ Create an empty queue for level order tarversal<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>queue<node *> q;<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ Enqueue Root and initialize height<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>q.push(root);<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>while<\/code> (1)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ nodeCount (queue size) indicates number of nodes<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ at current lelvel.<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>int<\/code> nodeCount = q.size();<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (nodeCount == 0)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>break<\/code>;<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ Dequeue all nodes of current level and Enqueue all<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ nodes of next level<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>while<\/code> (nodeCount > 0)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>node *node = q.front();<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>cout << node->data << <\/code>\" \"<\/code>;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>q.pop();<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (node->left != NULL)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>q.push(node->left);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>if<\/code> (node->right != NULL)<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>q.push(node->right);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>nodeCount--;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>}<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0<\/code>cout << endl;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>}<\/code><\/div>\n
}<\/code><\/div>\n
<\/div>\n
\/\/ Utility function to create a new tree node<\/code><\/div>\n
node* newNode(<\/code>int<\/code> data)<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>node *temp = <\/code>new<\/code> node;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>temp->data = data;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>temp->left = NULL;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>temp->right = NULL;<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>return<\/code> temp;<\/code><\/div>\n
}<\/code><\/div>\n
<\/div>\n
\/\/ Driver program to test above functions<\/code><\/div>\n
int<\/code> main()<\/code><\/div>\n
{<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>\/\/ Let us create binary tree shown in above diagram<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>node *root = newNode(1);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>root->left = newNode(2);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>root->right = newNode(3);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>root->left->left = newNode(4);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>root->left->right = newNode(5);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>root->right->right = newNode(6);<\/code><\/div>\n
<\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>printLevelOrder(root);<\/code><\/div>\n
\u00a0\u00a0\u00a0\u00a0<\/code>return<\/code> 0;<\/code><\/div>\n
}<\/code><\/div>\n<\/div>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n[ad type=”banner”]\n
Output:<\/p>\n
1\r\n2 3\r\n4 5 6<\/pre>\n","protected":false},"excerpt":{"rendered":"
Print level order traversal line by line – Given a binary tree, print level order traversal in a way that nodes of all levels are printed in separate lines.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,80140],"tags":[80964,80908,80909,80903,80906,80978,80910],"class_list":["post-27161","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-binay-tree","tag-binary-tree-level-order-traversal-leetcode","tag-level-order-traversal-example","tag-level-order-traversal-leetcode","tag-level-order-traversal-of-a-binary-tree-in-c-code","tag-level-order-traversal-of-binary-tree-using-queue-in-c","tag-level-order-traversal-using-queue-in-c","tag-print-tree-level-by-level-java"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27161","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27161"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27161\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}