vSPARROW

leetcode : Binary Tree Level Order Traversal

Posted on June 21, 2020

Solution with comments to describe the process of solving this problem

var levelOrder = function(root) {
    //result will be an array of arrays
    //  each subarray will include all the values of that depth
    //example subarry in position 1, is the 2nd element
    //  it will contain all values of the depth level of 2
    //another example is subarray in position 0, which is the 1st element
    //  it contains all values of depth 1, in this case the root's value
    const result = [] 
    // base case in case we get an empty tree
    if(!root){return result} 
    //just an array we will use as a queue
    //  we will work with elements in a FIFO (first-in-first-out) manner
    //  some places this listed as stack, but thats the wrong term
    //  as a stack is LIFO (last-in-first-out)
    const queue = [] 
    //we push our root onto our queue to get started
    queue.push(root)
    //as long as the queue exists we will go through the loop
    while(queue.length > 0){
        //row will be an array of all values of current depth
        const row = []
        //keeps treack of queue size for this depth
        //  this way we know how many elements to shift out of the queue
        //  and push the values onto row
        let queueSize = queue.length
        //in the loop we take a node, push its child nodes to queue
        //  then we push the value of node onto the row
        while(queueSize > 0){
            const node = queue.shift()
            if(node.left){queue.push(node.left)}
            if(node.right){queue.push(node.right)}
            row.push(node.val)
            queueSize--
        }
        //once all nodes of a certain depth have been evaluated
        //  we push the array row into result
        //  with its position in result being the depth
        result.push(row)
    }
    return result
};