# 102. Binary Tree Level Order Traversal — LeetCode(Python)

I got you!

# Problem:

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

**Example 1:**

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

**Output:** [[3],[9,20],[15,7]]

**Example 2:**

**Input:** root = [1]

**Output:** [[1]]

**Example 3:**

**Input:** root = []

**Output:** []

**Constraints:**

- The number of nodes in the tree is in the range
`[0, 2000]`

. `-1000 <= Node.val <= 1000`

# Solution:

## 1. Iterative BFS —

## Explanation —

We use a breadth first search (BFS) algorithm to solve this problem.

First, we create a queue to store the nodes that we come across and initialize it with the root node.

Now, we keep storing nodes in each level in our binary tree in our list *row.*

But, how do we do this?

At each iteration, we check the length of the queue, which tells exactly how many elements are there in a given level.

Then, we keep popping / dequeuing elements from our ** queue** and appending their children.

Note that we only pop ** l** number of elements at once and add them to our

**because our**

*row,**for*loop runs from

*0 to (l - 1).*This way, every node in the tree will be popped level wise and stored in the ** row** list.

After our *for* loop terminates, we append the ** row** list to our

**list.**

*ans*Finally, we return *ans.*

## Time and Space Complexity —

Since we are visiting each node in the tree only a constant number of times, we can say that our algorithm requires a linear amount of time to run.

Also, the queue could be storing as many as ** (n/2) **nodes at once, so we need a linear amount of auxiliary space.

Thus, if *n* is the number of nodes in our binary tree,

Time Complexity: O(n)

Space Complexity: O(n)

## 2. Recursive —

## Explanation —

We could also solve this problem recursively, and it is a good exercise since it helps us understand tree traversals better.

We use a helper function to write a depth-first search algorithm within.

The base case of our recursion would be when we reach a *NULL* node, in which case we just return from our function.

We use two variables in this helper function — ** ans,** which stores the final answer, and

**which tells us which level in the tree we’re at.**

*level,*If the length of our ** ans** array is smaller than the number of

**it means that we have entered into a new**

*levels,***so we need to extend our**

*level,***array to accommodate for newer nodes.**

*ans*We do this by appending an empty list to *ans.*

Next, we append the current node’s value to our ** ans.** The index at which we append this value is signified by the

**variable.**

*levels*Now, all we need to do is take the recursive leap of faith and call our function recursively, on the *left* and *right *subtrees.

Finally, we return *ans.*

## Time and Space Complexity —

Since we are visiting all nodes a constant number of times, we can say that our algorithm runs in linear time.

Also, the recursion stack might be storing all nodes in the tree in a really skewed tree (like a linked list), so we can say that we require a linear amount of auxiliary space.

Thus, if there are *n* nodes in the binary tree,

Time Complexity: O(n)

Space Complexity: O(n)