## Given problem

Given a binary tree, return the level order traversal of its node’s value.

The output of the above binary tree is:

``````1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7
``````

## Using recursive version

1. First way

Belows are some steps that we use.

• The first action we need to do is to calculate the maximum level of the tree.

• After we had the tree’s maximum level, we will iterate from level 1 to the maximum level, then get all elements of each level.

`````` public class MaxLevelTraversal {

private static int maxLevel = Integer.MIN_VALUE;

public static List<Integer> levelOrderTraversal(TreeNode root) {
List<Integer> nodes = new ArrayList<>();
getMaxLevelTopDown(root, 1);

for (int level = 1; level <= maxLevel; ++level) {
getNodesInSameLevel(root, level, 1, nodes);
}

return nodes;
}

public static void getNodesInSameLevel(TreeNode root, int currentLevel, int level, List<Integer> nodes) {
if (root == null) {
return;
}

if (level == currentLevel) {
}

getNodesInSameLevel(root.left, currentLevel, level + 1, nodes);
getNodesInSameLevel(root.right, currentLevel, level + 1, nodes);
}

private static void getMaxLevelTopDown(TreeNode root, int level) {
if (root == null) {
return;
}

if (root.left == null && root.right == null) {
maxLevel = Math.max(maxLevel, level);
}

getMaxLevelTopDown(root.left, level + 1);
getMaxLevelTopDown(root.right, level + 1);
}
}
``````
2. Second way

We will use hashmap to save nodes at each level.

`````` public class MaxLevelTraversal {

private static Map<Integer, List<Integer>> nodesPerLevel = new HashMap<>();

public static List<Integer> levelOrderTraversalRecursiveVersion1(TreeNode root) {
recursiveVersion(root, 0);

// convert hash map to list
if (nodesPerLevel.isEmpty()) {
return Collections.emptyList();
}

return nodesPerLevel.values().stream()
.flatMap(valNodes -> Stream.of(valNodes.toArray()))
.map(value -> (Integer) value)
.collect(Collectors.toList());
}

public static void recursiveVersion(TreeNode root, int level) {
if (root == null) {
return;
}

if (nodesPerLevel.size() == level) {
nodesPerLevel.put(level, new ArrayList<>());
}

// add the value of current node with the same level

recursiveVersion(root.left, level + 1);
recursiveVersion(root.right, level + 1);
}
``````

## Using iterative version

In this version, we will use Queue to save the children nodes of the current node.

``````class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}

queue.offer(root);

List<List<Integer>> levels = new ArrayList<>();

while (!queue.isEmpty()) {
List<Integer> currentLevel = new ArrayList<>();

int levelSize = queue.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode currentNode = queue.poll();

if (currentNode.left != null) {
queue.offer(currentNode.left);
}

if (currentNode.right != null) {
queue.offer(currentNode.right);
}
}

}

return levels;
}
}
``````

Below is the complexity of this way:

• Time complexity: O(n) with n is the number nodes in the tree.
• Space complexity: O(n)

## When to use

• When we want to work with the nodes that are in the same level such as applying in the peer-to-peer network, …

## Wrapping up

• Understanding about how to use Queue for the Level Order Traversal.

Refer:

https://leetcode.com/problems/binary-tree-level-order-traversal/