Problem Statement
Given a binary tree, populate an array to represent its level-by-level traversal. You should populate the values of all nodes of each level from left to right in separate sub-arrays.
Example 1:
Example 2:
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Why this is a Tree Level Order Traversal problem
| What the question says | The signal it matches |
|---|---|
| "populate an array to represent its level-by-level traversal" | the wording names a level |
| "nodes of each level from left to right in separate sub-arrays" | the output is a list of lists, one per level |
| recursion would reach node 4 before node 3 | your first idea is recursion, and it visits the nodes in an order that does not help |
Reading the queue's size before each round is the collect the levels variant.
The closest alternative. Depth First Search can produce this. Pass the depth down and append each value to the list for its level. It works, and it is a fine answer.
The queue version needs no depth argument and no growing list of lists. One round of the loop is already one level.
Solution
Since we need to traverse all nodes of each level before moving onto the next level, we can use the Breadth First Search (BFS) or Level Order traversal technique to solve this problem.
We can use a Queue to efficiently traverse a tree level-by-level. Here are the steps of our algorithm:
- Start by pushing the
rootnode to the queue. - Keep iterating until the queue is empty.
- In each iteration, first count the elements in the queue (let's call it
levelSize). We will have these many nodes in the current level. - Next, remove
levelSizenodes from the queue and push their value in an array to represent the current level. - After removing each node from the queue, insert both of its children into the queue.
- If the queue is not empty, repeat from step 3 for the next level.
Let's take the example-2 mentioned above to visually represent our algorithm:
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of the above algorithm is O(N), where N is the total number of nodes in the tree. This is due to the fact that we traverse each node once.
Space Complexity
The space complexity of the above algorithm will be O(N) as we need to return a list containing the level order traversal. We will also need O(N) space for the queue. Since we can have a maximum of N/2 nodes at any level (this could happen only at the lowest level), therefore we will need O(N) space to store them in the queue.