Given the root of a binary tree , return the level order traversal of the binary tree .
Level order traversal means picking nodes from left to right level by level.
For example,
For the below tree:
Level order traversal is [[3],[9,20],[15,7]]
It is a list of lists.
Each list represent the nodes at that level from left to right.
At level 0 we have only one node 3 .
At level 1 we have two nodes 9 and 20 from left to right.
At level 2 we have two nodes 15 and 7 from left to right.
Try out the solution here:
https://leetcode.com/problems/binary-tree-level-order-traversal/
Solution:
Use DFS or BFS
Approach 1 – Use Depth First Search
In Depth First Search , as usual you use recursion.
Make recursive calls for both the left node and right of each node at each level.
Every recursive call should have a base condition.
In this case the base condition is checking if the node is null or not.
If it is null return .
Else start the main logic.
Have a global list named output to hold the list of nodes at each level.
Have a global variable named level to keep track of each level in the recursive call.
In the recursive call , you check the current level.
If it is equal to the output size , then the list of nodes for the current level is not already in the output list.
So create a new list of nodes and add it to the current level.
If it is not equal to output size , then that level is already in the output list , so add the current node to that list.
Below is the logic to populate the output list data structure:
List<Integer> nodes = new ArrayList<>();
nodes.add(node.val);
if(output.size() == level ){
output.add(nodes);
}else{
output.get(level).add(node.val);
}
After the above step increment the level and make recursive calls on the left and right nodes of the current node.
Here is the logic:
int newlevel = level +1;
traverse(node.left,newlevel);
traverse(node.right,newlevel);
Here is the entire code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
List<List<Integer>> output = new ArrayList<>();
public List<List<Integer>> levelOrder(TreeNode root) {
traverse(root,0);
return output;
}
public void traverse(TreeNode node,int level){
if(node == null) return;
List<Integer> nodes = new ArrayList<>();
nodes.add(node.val);
if(output.size() == level ){
output.add(nodes);
}else{
output.get(level).add(node.val);
}
int newlevel = level +1;
traverse(node.left,newlevel);
traverse(node.right,newlevel);
return ;
}
}
Algorithm:
- Create two global variables : one to hold the output and one to track the current level of the tree while doing DFS
- Invoke a recursive function with the initial level 0 and the root node.
- In the recursive function do the following:
- If the node is null , return – this is the base condition.
- If it is not null , then find if the current level is already in the output list
- If it is not already present (output size == level) , then create a new list , add the current node value and add this list to the output list
- If it is already present , then add the current node value to the output list for the specific level
- Increment the level.
- Invoke the recursive call for the left node
- Invoke the recursive call for the right node
- After the recursive function , return the output.
Time complexity:
Since we traverse each node once time complexity is O(n)
Space complexity:
There is a recursive call made for each node , so size of recursion stack is O(n)
Approach 2 – Breadth First Search
In this case , as usual we use a queue.
Add the first node to the queue.
Then until the queue is empty do the following:
- Pop all elements in the queue and add it to the current level if it is already in the output list , else create a new list and add it to the output list
- Put the left node and the right node of each element in the current level to the queue
- Increment the level after processing all the elements in the current level.
Here is the code:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> output = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
int level = 0;
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
TreeNode node = queue.poll();
if(node == null) continue;
if(output.size() == level){
List<Integer> nodes = new ArrayList<Integer>();
nodes.add(node.val);
output.add(nodes);
}else{
output.get(level).add(node.val);
}
queue.add(node.left);
queue.add(node.right);
}
level++;
}
return output;
}
}
Note that at the end of every iteration of the while loop ,
We will have all the nodes of the next level of the tree in the queue.
Algorithm:
- Create an output list to hold the list of node values at each level of the tree
- Create a queue to do BFS
- Put the root node into the queue
- While queue is not empty do the following:
- Check queue size and then for each node in the queue do the following:
- Pop the node
- If it is null , then check the next node
- Check if the current level is present in the output list , if no create a new one , else add the current node to the current level
- Put the left node of the current node into the queue
- Put the right node of the current node into the queue
- After all the nodes of the current level are processed , increment the level
- After all the nodes in the queue are processed return the output.
Time complexity:
Since we traverse each node once , time complexity is O(n)
Space complexity:
Each node is put into the queue so we need a queue of space O(n)
That’s it!
Leave a Reply