This content originally appeared on DEV Community and was authored by Alkesh Ghorpade
Problem statement
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).
Problem statement taken from: https://leetcode.com/problems/binary-tree-level-order-traversal
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
Explanation
Recursive function
With trees, recursion is the most widely used approach as the code is easy to read. But for a few problems, recursion increases the time complexity. For large trees, recursion can result in stack overflow or because of O(N^2) time complexity will take a lot of time.
For this problem, we can use recursion, but we need to calculate the height of the tree.
A small C++ snippet of the above approach will look as below:
void printLevelOrder(node* root){
int h = height(root);
for (int i = 0; i < h; i++)
printCurrentLevel(root, i);
}
void printLevel(node* root, int level){
if (root == NULL)
return;
if (level == 0)
cout << root->data << " ";
else if (level > 0) {
printLevel(root->left, level - 1);
printLevel(root->right, level - 1);
}
}
The time complexity of the above approach is O(N^2) for skewed trees. The worst-case space complexity is O(N).
Iterative approach
We can improve the time complexity by using a queue as a data structure. Let's check the algorithm.
- initialize 2D array as vector vector<vector<int>> result
- initialize size and i
- return result if root == null
- initialize queue<TreeNode*> q
- push root to queue : q.push(root)
- initialize TreeNode* node for iterating on the tree
- loop while( !q.empty() ) // queue is not empty
- initialize vector<int> tmp
- set size = q.size()
- loop for i = 0; i < size; i++
- set node = q.front()
- if node->left
- push in queue: q.push(node->left)
- if node->right
- push in queue: q.push(node->right)
- remove the front node: q.pop()
- push the tmp to result: result.push_back(tmp)
- return result
C++ solution
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> result;
int size, i;
if(root == NULL)
return result;
queue<TreeNode*> q;
q.push(root);
TreeNode* node;
while(!q.empty()){
vector<int> tmp;
size = q.size();
for(i = 0; i < size; i++){
node = q.front();
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
q.pop();
tmp.push_back(node->val);
}
result.push_back(tmp);
}
return result;
}
};
Golang solution
func levelOrder(root *TreeNode) [][]int {
result := [][]int{}
queue := []*TreeNode{root}
for len(queue) != 0 {
tmp := []int{}
size := len(queue)
for i := 0; i < size; i++ {
if queue[0] != nil {
tmp = append(tmp, queue[0].Val)
queue = append(queue, queue[0].Left)
queue = append(queue, queue[0].Right)
}
queue = queue[1:]
}
result = append(result, tmp)
}
return result[:len(result)-1]
}
Javascript solution
var levelOrder = function(root) {
let result = [];
let queue = [];
if(root)
queue.push(root);
while(queue.length > 0) {
tmp = [];
let len = queue.length;
for (let i = 0; i< len; i++) {
let node = queue.shift();
tmp.push(node.val);
if(node.left) {
queue.push(node.left);
}
if(node.right) {
queue.push(node.right);
}
}
result.push(tmp);
}
return result;
};
Let's dry-run our algorithm to see how the solution works.
Input: root = [3, 9, 20, null, null, 15, 7]
Step 1: vector<vector<int>> result;
int size, i;
Step 2: root == null
[3, 9..] == null
false
Step 3: queue<TreeNode*> q;
q.push(root);
q = [3]
Step 4: loop !q.empty()
q = [3]
q.empty() = false
!false = true
vector<int> tmp
size = q.size()
= 1
for(i = 0; i < 1; i++)
- 0 < 1
- true
node = q.front()
node = 3
if node->left
- node->left = 9
- q.push(node->left)
- q = [3, 9]
if node->right
- node->right = 20
- q.push(node->right)
- q = [3, 9, 20]
q.pop()
q = [9, 20]
tmp.push_back(node->val)
tmp.push_back(3)
i++
i = 1
for(i < 1)
1 < 1
false
result.push_back(tmp)
result = [[3]]
Step 5: loop !q.empty()
q = [9, 20]
q.empty() = false
!false = true
vector<int> tmp
size = q.size()
= 2
for(i = 0; i < 2; i++)
- 0 < 2
- true
node = q.front()
node = 9
if node->left
- node->left = nil
- false
if node->right
- node->right = nil
- false
q.pop()
q = [20]
tmp.push_back(node->val)
tmp.push_back(9)
i++
i = 1
for(i < 2)
- 1 < 2
- true
node = q.front()
node = 20
if node->left
- node->left = 15
- q.push(node->left)
- q = [20, 15]
if node->right
- node->left = 7
- q.push(node->right)
- q = [20, 15, 7]
q.pop()
q = [15, 7]
tmp.push_back(node->val)
tmp.push_back(20)
tmp = [9, 20]
i++
i = 2
for(i < 2)
- 2 < 2
- false
result.push_back(tmp)
result = [[3], [9, 20]]
Step 6: loop !q.empty()
q = [15, 7]
q.empty() = false
!false = true
vector<int> tmp
size = q.size()
= 2
for(i = 0; i < 2; i++)
- 0 < 2
- true
node = q.front()
node = 15
if node->left
- node->left = nil
- false
if node->right
- node->right = nil
- false
q.pop()
q = [7]
tmp.push_back(node->val)
tmp.push_back(15)
i++
i = 1
for(i < 2)
- 1 < 2
- true
node = q.front()
node = 7
if node->left
- node->left = nil
- false
if node->right
- node->right = nil
- false
q.pop()
q = []
tmp.push_back(node->val)
tmp.push_back(7)
tmp = [15, 7]
i++
i = 2
for(i < 2)
- 2 < 2
- false
result.push_back(tmp)
result = [[3], [9, 20], [15, 7]]
Step 7: loop !q.empty()
q = []
q.empty() = true
!true = false
Step 8: return result
So we return the result as [[3], [9, 20], [15, 7]].
This content originally appeared on DEV Community and was authored by Alkesh Ghorpade
Print
Share
Comment
Cite
Upload
Translate
Updates
There are no updates yet.
Click the Upload button above to add an update.
APA
MLA
Alkesh Ghorpade | Sciencx (2021-11-18T18:28:32+00:00) LeetCode – Binary Tree Level Order Traversal. Retrieved from https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/
" » LeetCode – Binary Tree Level Order Traversal." Alkesh Ghorpade | Sciencx - Thursday November 18, 2021, https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/
HARVARDAlkesh Ghorpade | Sciencx Thursday November 18, 2021 » LeetCode – Binary Tree Level Order Traversal., viewed ,<https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/>
VANCOUVERAlkesh Ghorpade | Sciencx - » LeetCode – Binary Tree Level Order Traversal. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/
CHICAGO" » LeetCode – Binary Tree Level Order Traversal." Alkesh Ghorpade | Sciencx - Accessed . https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/
IEEE" » LeetCode – Binary Tree Level Order Traversal." Alkesh Ghorpade | Sciencx [Online]. Available: https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/. [Accessed: ]
rf:citation » LeetCode – Binary Tree Level Order Traversal | Alkesh Ghorpade | Sciencx | https://www.scien.cx/2021/11/18/leetcode-binary-tree-level-order-traversal/ |
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.