Binary Tree Level Order Traversal
Problem
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: []
Pseudocode
- bfs is more suited as it traverses breath first
- solution is dfs lol
- just have to track each level while traversing left and right child
- push node value in the same array index
- i.e. root node, 0, goes into arr[0]
- first left and right child nodes, count 1, goes into arr[1] etc..
Solution
// https://leetcode.com/problems/binary-tree-level-order-traversal/
var levelOrder = function (root) {
let output = [];
if (!root) {
return [];
}
function walk(node, count) {
// base condition
if (!node) {
return;
}
// pre
if (!output[count]) {
output.push([]);
}
// push into output array of the same level
output[count].push(node.val);
// recurse
walk(node.left, count + 1);
walk(node.right, count + 1);
// post
}
walk(root, 0);
return output;
};
Time and Space Complexity
Time
What did the code do
Total -
Space
What did the code do
Total -
Last updated