Given a binary tree, the task is to traverse it level by level or perform level order (breadth first) traversal on it.

##### Example 1: Breadth First traversal of a Binary Tree

Input:

**Output: **1,7,9,2,6,9,5,11,5

## Solutions

### Method 1: With the help of 2 functions

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".

##### Complexity

**O(n**in worst case and space complexity is

^{2})**O(n)**due to recursive calls..

### Method 2: Using Queue

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.

##### Complexity

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

### Method 3: Using a Map

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).

##### Complexity

**O(n)**and space complexity is also

**O(n)**.