Level Order or Breadth First traversal of Binary Tree

We can solve this problem using two functions, one to traverse the tree level by level and other to print a particular level.

First we need to calculate height of the tree, now call "printOneLevel" for "0-n", print one level each time.

The "printOneLevel" function will keep on traversing the tree from root each time and will print nodes only if current "level" is equals to "levelToPrint".

The idea is to use a "queue" to hold nodes, add "root" to queue.

While queue is not empty, "poll" an element print it and if left/right is not 'null' add them to the queue.

The time complexity of this solution is O(n) and space complexity is also O(n).

The idea is to traverse the tree and store its nodes by level in a map and print the map level by level.

We need to create a "map <level, set<node>>", a recursive function "populateMap" will populate values in the map; if current node has right/left node increase level by one and call "populateMap" on it.

Print the map at the end, make sure to use "LinkedHashMap" because we need the map to retain sorted order of keys (level).