Binary Tree Level Order Traversal
Problem Description
Question
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
Solve it on LeetCode
Approaches
1. Iterative using Queue (Breadth-First Search)
Intuition:
The most intuitive way to achieve level order traversal is by using a queue (FIFO) data structure. The idea is to process each level of the binary tree one at a time, adding child nodes to the queue as we go. This way, we ensure nodes are processed level by level.
Steps:
- Initialize an empty
Queueand an empty listresult. - Add the root of the tree to the queue.
- While the queue is not empty:
- Determine the number of nodes at this level (
sizeof the queue). - For each node in the current level, remove the node from the queue and add its value to a temporary list.
- Add the left and right children (if they exist) to the queue.
- After processing all nodes at this level, add the temporary list to the result.
- Finally, return the
resultlist which contains nodes level by level.
Code:
Complexity Analysis
- Time Complexity: O(N) - Each node is processed exactly once.
- Space Complexity: O(N) - Holds up to N/2 nodes in the queue for the most balanced tree, which simplifies to O(N).
2. Recursive using Depth-First Search
Intuition:
An alternative is to use recursion to perform a depth-first search, keeping track of the depth of the current node. The goal is to add each node to a list that corresponds to its depth level.
Steps:
- Define a helper function that:
- Takes the current node, depth, and the result list.
- If the current node is null, return immediately.
- If the current depth matches the size of the result list, create a new list at that depth.
- Add the current node's value to its corresponding depth in the result list.
- Recurse deeper into the tree by calling the function for the left and right children.
- Call the helper function starting with the root node at depth 0.
- Return the
resultlist containing the nodes level by level.
Code:
Complexity Analysis
- Time Complexity: O(N) - Each node is visited once.
- Space Complexity: O(N) - Potentially O(H) for the recursion stack, where H is the height of the tree. However, the result list also uses space proportional to N in the worst case.