Binary Tree Level Order Traversal

Binary Tree Level Order Traversal - LeetCodeLeetCode

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 -