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 row, because our 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 ans list.
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 level, which tells us which level in the tree we’re at.
If the length of our ans array is smaller than the number of levels, it means that we have entered into a new level, so we need to extend our ans array to accommodate for newer nodes.
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 levels variable.
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)
