102. Binary Tree Level Order Traversal

Description

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

My Solution

Source Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[][]}
 */
let levelOrder = function(root) {
    //check if the tree is empty first
    if(!root){
        return [];
    }
    
    let discovered = [root];
    let levels = [];
    
    while(discovered.length){
        let levelArr = []

        //at this point, all the nodes in the queue belong to same level
        //look at the children of each node in the queue and unqueue them
        let numInCurrentLevel = discovered.length;
        for(let i = 0; i < numInCurrentLevel; i++){
                    let node = discovered.shift();
                    levelArr.push(node.val);
            
                    if(node.left){
                        discovered.push(node.left)
                    }
                    if(node.right){
                        discovered.push(node.right)
                    }
        }
        
        levels.push(levelArr)
        
    }
    
    return levels;
};

Analysis

This is basically just breadth-first search. The only difference here is that we need to keep track of which nodes are in which level so it's not as simple as just regular BFS. To start, we create a queue for nodes we discover as we traverse the tree and enqueue the root. We then add the root to the list of nodes on the current level. Then enqueue the root's children and add the list of nodes at that level to the main list of lists of nodes. We then "move" to the next level and repeat this process until the queue is empty.

We visit every node in the tree exactly once so the running time is just O(n) where n is the number of nodes.