Given a binary tree, print its nodes level by level. i.e. all nodes present at level 1 should be printed first followed by nodes of level 2 and so on.. All nodes for any level should be printed from left to right.

For example, the level order traversal for below tree is 1, 2, 3, 4, 5, 6, 7

We have already discussed preorder, inorder and post-order traversals of the binary tree which are nothing but variations of Depth-first search of a Tree. Trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This search is referred to as level order traversal or breadth-first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.

Simple solution would be to print all nodes of level 1 first, followed by level 2, .. till level h where h is the height of the tree. All nodes present in a level can be printed by modifying pre-order traversal of the tree.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to print all nodes of a given level from left to right bool printLevel(Node* root, int level) { if (root == nullptr) return false; if (level == 1) { cout << root->key << " "; // return true if at-least one node is present at given level return true; } bool left = printLevel(root->left, level - 1); bool right = printLevel(root->right, level - 1); return left || right; } // Function to print level order traversal of given binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) return; // start from level 1 -- till height of the tree int level = 1; // run till printLevel() returns false while (printLevel(root, level)) level++; } |

The time complexity of above solution is O(n^{2}).

We can reduce time complexity to O(n) by using extra space. Below is pseudocode for a simple queue based level order traversal which require space proportional to the maximum number of nodes at a given depth. This can be as much as the total number of nodes / 2.

**levelorder(root)**

q -> empty queue

q.enqueue(root)

while (not q.isEmpty())

node -> q.dequeue()

visit(node)

if (node.left <> null)

q.enqueue(node.left)

if (node.right <> null)

q.enqueue(node.right)

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // Function to print level order traversal of given binary tree void levelOrderTraversal(Node* root) { if (root == nullptr) return; // create an empty queue and enqueue root node list<Node*> queue; queue.push_back(root); // pointer to store current node Node* curr = nullptr; // run till queue is not empty while (queue.size()) { // process each node in queue and enqueue their // non-empty left and right child to queue curr = queue.front(); queue.pop_front(); cout << curr->key << " "; if (curr->left) queue.push_back(curr->left); if (curr->right) queue.push_back(curr->right); } } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

We can also solve this problem by using hashing. The idea is to traverse the tree in preorder fashion and store every node and its level into the multimap using level number as a key. Finally, we print all nodes corresponding to every level starting from first level. We can also traverse the tree in inorder or postorder fashion.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// Data structure to store a Binary Tree node struct Node { int key; Node *left, *right; }; // traverse the tree in pre-order fashion and store nodes into the map // corresponding to their level void preorder(Node *root, int level, auto &map) { // base case: empty tree if (root == nullptr) return; // insert current node and its level into the map map[level].push_back(root->key); // recurse for left and right subtree by increasing level by 1 preorder(root->left, level + 1, map); preorder(root->right, level + 1, map); } // Recursive function to print level order traversal of given binary tree void levelOrderTraversal(Node *root) { // create an empty map to store nodes between given levels map<int, vector<int>> map; // traverse the tree and insert its nodes into the map // corresponding to the their level preorder(root, 1, map); // iterate through the map and print all nodes present in very level for (auto it: map) { cout << "Level " << it.first << ": "; for (int i: it.second) cout << i << " "; cout << endl; } } |

The time complexity of above solution is O(n) and auxiliary space used by the program is O(n).

**Exercise:** Modify the solution to print nodes of different levels in separate line.

**References:** https://en.wikipedia.org/wiki/Tree_traversal

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂

## Leave a Reply

can you please explain how the complexity in o(n^2)?

Rahul, thanks for sharing your concerns.

printLevel()function takesO(n)times as it traverse the whole tree once and we’re callingprintLevel()function for each level of the tree. And the number of levels in a binary tree can be equal to number of nodes for skewed trees. So the complexity isO(nin worst case. Hope you’re clear now.^{2})Ok. I thought the code was for balanced trees. But it is for trees in general.

Thanks.

Sorry. I’m unclear on why printLevel() takes O(n), and confused about the part saying that it traverses the whole tree once. I thought printLevel() is doing only 1 level at a time, so for a balanced tree for example, level 1 is O(1) for level 1and level 2i O(2)… , and the combination of all printLevel() calls in the levelOrderTraversal() is O(n) as it parses all N nodes. For an unbalanced tree, assuming the tree is all a left branch, then each level is O(1) and all levels are O(n). Could you please help clarify? Thanks!

This helped me understand level order traversal better. Thanks for the great examples with runtime complexity mentioned!