vSPARROW

leetcode : Maximum Depth of Binary Tree : Iterative solution

Posted on June 20, 2020

Here is a iterative solution on the Max Depth of a tree problem. I solved it using recursion, but then tried to solve it using an iterative process. I added comments and some extra variables for readability to make them easier to follow along

var maxDepth = function(root, depth=0) {
    //base case: if we are given an empty or null LinkedList return 0
    if(!root){return 0}
    //construct the array which will hold nodes
    let a = []
    //currently max is 0. As we traverse tree, it will grow
    let max = 0
    //initialize the array by adding a node, and node depth
    //in this case root and 1
    a.push([root,1])
    //loop through while array has elements
    while(a.length > 0){
        //I added the following variables for readability so 
        //if you are learning its easier to follow along
        let node = a[0][0]
        let depth = a[0][1]
        //if the node has a left node or right node
        //add the left and right to the array
        //while incrementing the depth, because
        //left or right is 1 deeper then current depth
        if(node.left){a.push([node.left,depth+1])}
        if(node.right){a.push([node.right,depth+1])}
        //here we update the max if the depth found is greater
        if(a[0][1] > max){max = a[0][1]}
        //we remove the node because we no longer need it
        a.shift()
    }
    return max
};