15) Maximum Depth of Binary Tree

I tried this problem with Paul winkler. My approach was to define a recursion function inside of the main function and mutate a global depth variable, but as I worked through it realized I faced a challenge which was that I didn’t really have a way to make sure that the left and right nodes didn’t BOTH increment the global depth. I had sort of found a fake solution to this, which was incredibly stupid:

if (root){
	let localDepth = globalDepth += 1
	if (localDepth > globalDepth){
		glovalDepth = localDepth
	}
}

I’m…still not exactly sure what I was thinking here. This is a really verbose way of just saying globalDepth++ 😂

But clearly when I wrote it I thought that somehow I could trick logic into only incrementing under some special condition, which never seemed to show up.

Ultimately, I found that a pure functional recursive approach worked great! Here it is along with my psuedocode:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
// Return maximum depth - the number of nodes along the longest path from the root node to the farthest leaf node
 
function maxDepth(root: TreeNode | null): number {
    function recursiveMaxDepth(root: TreeNode | null, depth:number = 0): number {
        if (!root) return depth// end of computation base case
 
        // I cannot be doing this for both branches
 
        // let localDepth = globalDepth
        // localDepth += 1
        //if (localDepth > globalDepth){
        //    globalDepth = localDepth // mutation
        //}
        // I am trying to increment the global depth by 1
        // for every generation
        // checking if it's already been done for that generation
        const leftDepth = recursiveMaxDepth(root.right, depth + 1)
        const rightDepth = recursiveMaxDepth(root.left, depth + 1)
        return Math.max(leftDepth, rightDepth)
 
    }
    return recursiveMaxDepth(root)
    // return globalDepth
 
    // edge case - initial root is null (make sure depth has been given initial value 0)
    // some leafs are null, 
 
    // Can't return 
 
    // local depth will start as 0 - done
    // recursively start with the root node - done
    // If it exists (recursive case) 
    // increment depth by 1,
    // If it's null (base case)
    // return 
    // do two recursive cases, one for each leaf
    // We have to have a base case that returns the depth
    // I think I will make a global variable, set it to 0
    // and during base case, if the value of the current node is 0
    // Check and see if the depth that we have at that point is greater than global depth
    // If it is, set global depth
 
    // Once done with recursion, return the global depth
    
};

Time it took me to get to this code^: 26 minutes

Note

Can I do this without recursion? No I cannot. It would be useful to learn how to do that.

Despite the carnage I got when I ran this and generally got an extra increment for every generation of depth initially, I am proud of the eloquence of my final solution. If I just remove it from it’s parent function in which it’s needlessly encased, I get this:

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */
 
// Return maximum depth - the number of nodes along the longest path from the root node to the farthest leaf node
 
function maxDepth(root: TreeNode | null, depth:number = 0): number {
        if (!root) return depth
        const leftDepth = maxDepth(root.right, depth + 1)
        const rightDepth = maxDepth(root.left, depth + 1)
        return Math.max(leftDepth, rightDepth)
};

Not bad! That’s probably the first time I’ve gotten to a five-line function on my own in less than half an hour.

It never ceases to amaze me the way code works - how much more available a 40 line function is than a four or five line solution, even though the latter looks so simple when I look at it.