Leetcode 75: 102. Binary Tree Level Order Traversal
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
Solution: Using a recursive approach
- One way is to have a function to print a given level of a binary tree.
- Using the height utility function, we can iterate over all the available levels of a tree, and then call the above
returnCurrentLevel
function, and keep adding the list from every level to our resultant level. - Obviously, this will involve visiting nodes multiple times, and will be slow.
- This is a O(n^2) approach.
- In the returnCurrentLevel function,
- If the root is null, then return.
- Once the original level (provided as an input) becomes, print the node. Because that's what will happen, as we keep decrementing the level going from level 1 to n.
- If the current level > 1,
- call the returnCurrentLevel function on both root.left, and root.right nodes and at the same time, decrement the level by 1.
Code:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
int height = height(root);
for(int i = 1; i <= height; i++){
List<Integer> temp = new ArrayList<>();
returnCurrentLevel(root, i, temp);
res.add(temp);
}
return res;
}
static int height(TreeNode root){
if(root == null) return 0;
return 1 + Math.max(height(root.left), height(root.right));
}
static void returnCurrentLevel(TreeNode root, int level, List<Integer> temp){
if(root == null) return;
if(level == 1) {
temp.add(root.val);
return;
} else if(level > 1){
returnCurrentLevel(root.left, level - 1, temp);
returnCurrentLevel(root.right, level - 1, temp);
}
}
}
Complexity:
- Time: O(N^2) in worst case.
- Space: O(N) in worst case. (for skewed tree). For balanced tree, call stack uses O(logN) space.
Solution: Using Queue
- Initialize a queue of TreeNodes.
- 'Offer' the root node.
- Now, while the queue is not empty, do the following:
- Get the count of the elements in the queue. This gives us the number of elements at the current level of Binary Tree.
- Initialize a new temp ArrayList.
- Loop over the count number of elements in the queue. (i = 0 to count - 1)
- Keep adding the left, and right child of each of the above elements in the queue.
- Once that is done, add the value of the ith node to the temp ArrayList, and poll the ith node.
- Add the temp ArrayList to the wrapperList (res). This count list of lists of elements of every level.
- This is the O(n) approach since we visit every node only once.
- Space: We will storing all the nodes atleast once in the queue. So, it's proportional to the number of nodes in the tree.
Code:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if(root == null) return res;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while(!queue.isEmpty()){
int count = queue.size();
List<Integer> temp = new ArrayList<>();
for(int i = 0; i < count; i++){
if(queue.peek().left != null) queue.offer(queue.peek().left);
if(queue.peek().right != null) queue.offer(queue.peek().right);
temp.add(queue.poll().val);
}
res.add(temp);
}
return res;
}
}
Complexity:
- Time: O(N)
- Space: O(N)