| Question | 102. Binary Tree Level Order Traversal – Leetcode Javascript Solution |
| Difficulty | Medium |
| Question Type | Tree, Binary Tree |
| Question Link | https://leetcode.com/problems/binary-tree-level-order-traversal/ |
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]]
Explanation: From root node, we have to return each level of siblings by order of tree.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 <= 1000What is Level Order Traversal?
Level Order Traversal is the algorithm to process all nodes of a tree by traversing through depth, first the root, then the child of the root, etc.
Solution 1 : ( Using Depth First Search [ DFS ] )
Depth First Search(DFS) is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
DFS algorithm is a recursive algorithm that uses the idea of backtracking
// ------ Level Order Travesal Leetcode solution start - jsdiet ------
let levelOrder = (root) => {
if (!root) {
return [];
}
let result = [];
const dfs = (node, level) => {
if (!node) {
return;
}
if (!result[level]) {
result[level] = [node.val];
} else {
result[level].push(node.val);
}
dfs(node.left, level + 1);
dfs(node.right, level + 1);
}
dfs(root, 0);
return result;
};
// ------ Level Order Travesal Leetcode solution end - jsdiet ------
// Leetcode environment provides already generated binary tree.
// So below part of code no need, if you are trying in Leetcode website environment.
// ------- Code to generate our binary tree -------
// This is purely for testing in local machine
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length < 0) {
let current = queue.shift();
for (let side of ['left', 'right']) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
const tree = new TreeNode(3);
tree.insert([9, 20, 4, 1, 5, 7, null, null, 2, null, null, null]);
// Execute using DFS
let val = levelOrder(tree);
console.log(val);Complexity Analysis :
Time complexity: O(n2)
Space complexity: O(n)
Time complexity: O(n2) in worst case. For a skewed tree(binary tree, which is dominated solely by left child nodes or right child nodes), dfs() takes O(n) time where n is the number of nodes in the skewed tree. So time complexity of printLevelOrder() is O(n) + O(n-1) + O(n-2) + .. + O(1) which is O(n^2).
In DFS, we might traverse through more edges to reach a destination vertex from a source. DFS is more suitable when there are solutions away from source. Here, children are visited before the siblings. Hence our goal is to traverse through siblings first, so Breadth First Search will be the better solution in this scenarior. Lets see how we can optimize above problem with BFS approach.
Solution 2 ( Using Breadth First Search [ BFS ] ) : ==> Optimized
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level. BFS builds the tree level by level.
// ------ Level Order Travesal Leetcode solution start - jsdiet ------
let levelOrder = (root) => {
// If root is null return an empty array
if (!root) {
return [];
}
const queue = [root]; // initialize the queue with root
const traversalOrder = []; // declare output array
while (queue.length) {
const order = [];
let length = queue.length, count = 0;
while (count < length) {
const node = queue.shift();
order.push(node.val);
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
count++;
}
traversalOrder.push(order);
}
return traversalOrder;
};
// ------ Level Order Travesal Leetcode solution end - jsdiet ------
// Leetcode environment provides already generated binary tree.
// So below part of code no need, if you are trying in Leetcode website environment.
// ------- Code to generate our binary tree -------
// This is purely for testing in local machine
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ['left', 'right']) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
const tree = new TreeNode(3);
tree.insert([9, 20, 4, 1, 5, 7, null, null, 2, null, null, null]);
// Execute using BFS
let val = levelOrder(tree);
console.log(val);Complexity Analysis :
Time complexity: O(n)
Space complexity: O(n)
In the best case of time complexity, we can achieve by O(n), since we are using BFS tree to visit each node by only once, So in that case we will be having O(n) time complexity.
BFS is better approach compare to DFS, while finding each level of siblings.
If you have any doubts, add in comment section. Will clarify at my level best. Also, if you have better solution, kindly share it, will grow together as to become better engineer.
