Grind 75 Question 24: Maximum Depth of Binary Tree

I got it! In 20 minutes! With a little past-problem help!

The Problem

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

The First Attempts

I’m trying to pound through these as fast as I can and finish Week 2 today (Monday), so there won’t be much explanation to this code besides: I tried to whiteboard it since I’ve got recursion semi-fresh in my mind, but it didn’t go extremely well. Heh.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {

	let deepest = 0;
    	function dfs(tree) {
		if (tree == null) return -1;
		dfs(tree.right)
		dfs(tree.left)
		
		
		let deepest = Math.max(deepest, right, left)
}
	return deepest;
};

The Solution

I knew deep down that I didn’t need Neetcode for this one — it’s just recursion, like the problem I solved a couple hours ago — so I kept on plugging and used Diameter of Binary Tree as my code example.

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var maxDepth = function(root) {

	let deepest = 0;
    function dfs(tree) {
        if (tree == null) return 1;
        let right = dfs(tree.right)
        let left = dfs(tree.left)
        
        deepest = (Math.max(deepest, right, left))
        return 1 + Math.max(right, left)    
    }
	dfs(root);
    return deepest;
};

And what do you know? I got it! I kept having to adjust what happened once the tree got down to null, and it turns out returning 1 was the answer. I didn’t think it would be accepted, but it was!

Here’s the quick and dirty of what’s going on, which is very similar/slightly less complicated than the diameter question:

1. Initialize deepest as 0 for returning at the end.
2. Write the recursive function:
   1. If the bottom of the tree is reached, return 1
   2. Run the recursion on the right and left
   3. Set deepest as the biggest number between deepest, right, and left
   4. Return 1 + whatever is the maximum between right and left. I vaguely understand this — you’re wanting to add 1 to the level you’re on to get the level number — but why Math.max()?
3. Do the depth-first-search on root
4. Return deepest!

What I Learned

1. I can do it! I can do recursion! Almost on my own!
2. But in all seriousness — more work with binary trees and depth-first searches.

Related Posts

F

Five Things for May 10

A

April Recap, May Intentions

F

Five Things for April 26