# Binary Tree Level Order Traversal (Leetcode 102)

Difficulty : Medium Link: Day 12: May Leetcode Challenge

## Problem Description

Given the `root` of a binary tree, return the level order traversal of its nodes’ values. (i.e., from left to right, level by level).

### Examples

``````Input: root = [3,9,20,null,null,15,7]
Output: [,[9,20],[15,7]]
``````
``````Input: root = 
Output: []
``````
``````Input: root = []
Output: []
``````

### Constraints

• The number of nodes in the tree is in the range `[0, 2000]`.
• `-1000 <= Node.val <= 1000`

# Solution

### Recursive

The first approach could to start recursively since its intuitive. We can pass another parameter for level and further incrementing it by every call, thus marking the change of levels. This approach would of course we slow and for every new level we will have to iterate older levels every time.

### Breadth-First Search

A BFS approach involves the use of a data structure called Queue(q) so that we deal with the nodes of the tree in the proper order. The queue operates in a First In First Out (FIFO) order, so insertions would be at the end and removing from the front. We can use that property and we can calculate the number of items to be processed in the next level by finding the count of elements in the queue after every iteration.

## Complexity Analysis

• Time complexity = O(N) since each node is processed exactly once.
• Space complexity = O(N) to keep the output structure which contains `N` node values