Friday, 14 July 2017 12:27

Print level order traversal line by line | Set 1

Written by
Rate this item

Given a binary tree, print level order traversal in a way that nodes of all levels are printed in separate lines.

For example consider the following tree

1
/     \
2       3
/   \       \
4     5       6
/  \     /
7    8   9

Output for above tree should be
1
2 3
4 5 6
7 8 9
/* Function to line by line print level order traversal a tree*/
void printLevelOrder(struct node* root)
{
int h = height(root);
int i;
for (i=1; i<=h; i++)
{
printGivenLevel(root, i);
printf("\n");
}
}

/* Print nodes at a given level */
void printGivenLevel(struct node* root, int level)
{
if (root == NULL)
return;
if (level == 1)
printf("%d ", root->data);
else if (level > 1)
{
printGivenLevel(root->left, level-1);
printGivenLevel(root->right, level-1);
}
}

The time complexity of the above solution is O(n2)

How to modify the iterative level order traversal (Method 2 of this) to levels line by line?
The idea is similar to this post. We count the nodes at current level. And for every node, we enqueue its children to queue.

 /* Iterative program to print levels line by line */ #include #include using namespace std;   // A Binary Tree Node struct node {     struct node *left;     int data;     struct node *right; };   // Iterative method to do level order traversal line by line void printLevelOrder(node *root) {     // Base Case     if (root == NULL)  return;       // Create an empty queue for level order tarversal     queue q;       // Enqueue Root and initialize height     q.push(root);       while (1)     {         // nodeCount (queue size) indicates number of nodes         // at current lelvel.         int nodeCount = q.size();         if (nodeCount == 0)             break;           // Dequeue all nodes of current level and Enqueue all         // nodes of next level         while (nodeCount > 0)         {             node *node = q.front();             cout << node->data << " ";             q.pop();             if (node->left != NULL)                 q.push(node->left);             if (node->right != NULL)                 q.push(node->right);             nodeCount--;         }         cout << endl;     } }   // Utility function to create a new tree node node* newNode(int data) {     node *temp = new node;     temp->data = data;     temp->left = NULL;     temp->right = NULL;     return temp; }   // Driver program to test above functions int main() {     // Let us create binary tree shown in above diagram     node *root = newNode(1);     root->left = newNode(2);     root->right = newNode(3);     root->left->left = newNode(4);     root->left->right = newNode(5);     root->right->right = newNode(6);       printLevelOrder(root);     return 0; }

Output:

1
2 3
4 5 6 