Maximum Depth of Binary Tree in JavaScript

Question

The task

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.

Example 1: Input: root = [3,9,20,null,null,15,7] Output: 3

      3
     / \
    /   \
   9    20
        / \
       15  7

Example 2: Input: root = [1,null,2] Output: 2

My solution:

/**
 * 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}
 */
const maxDepth = (root) => {
    if (root === null) {
        return 0;
    }
    return iterateTree(root, 1);
};

const iterateTree = (root, level) => {
    const isLeftTreeMissing = root.left === null;
    const isRightTreeMissing = root.right === null
    
    let leftLevel = level;
    let rightLevel = level;
    
    if (isLeftTreeMissing === false) {
        leftLevel = iterateTree(root.left, level + 1);
    }
    if (isRightTreeMissing === false) {
        rightLevel = iterateTree(root.right, level + 1);
    }
    return leftLevel > rightLevel ? leftLevel : rightLevel;
};

Answer 1

A few minor style suggestions for starters:

• Use const instead of let. let says "I'm going to reassign this variable later" but then you never do, so const is safer and communicates your intent best.
• if (isLeftTreeMissing === false) { is clearer as if (!isLeftTreeMissing) {.
• I'm generally not crazy about the pattern of breaking out separate variables:

  const isSomethingNull = something === null;
  
  if (isSomethingNull) { ... }
  

  I'd just inline the condition since it's so small (if it wasn't, I'd write a function):

  if (something === null) { ... }
  

  which pretty much reads like English, is easier to understand than the extra layer of indirection and eliminates the potential for a bug to creep in if something unexpected happens to that variable between the assignment and the conditional test. Good to see you're using === though!
• If you're testing whether objects exist and the contract for the function is that the parameter is either an object or null, I'd use if (!something) {.

---

The bigger issue is the presence of two really common antipatterns in recursion -- I'd call these almost universal "beginner recursion" mistakes (but don't take that the wrong way; I did it this way too!).

The first is the tendency to make decisions about root.left and root.right from the parent frame. In general, it adds complexity, isn't necessary and disrupts the magical part of recursion: after you code up the logic for your frame's data, magically let the children apply the same pattern and hand you their results. Don't dip into and mess with the children's data unless you must.

Better is to let the child calls handle the parent's root.left? as root? itself, after the call to maxDepth(root.left). This simplifies the code quite dramatically and is more natural:

const maxDepth = root => root
  ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right))
  : 0
;

/*
   3
   / \
  /   \
 9    20
      / \
     15  7
*/
const tree = {
  val: 3,
  left: {val: 9},
  right: {
    val: 20,
    left: {val: 15},
    right: {val: 7},
  },
};
console.log(maxDepth(tree));

This code should reveal the second common/universal recursion mistake I see: overcomplicating return values and parameters. Generally speaking, data flows one way: results flow back up the tree and state flows down. But if you're passing the same data representing the results down and then back up without really operating on it, as is the case in your code, oftentimes the downward-flowing data is pointless. You can see I've done away with the unnecessary parameter in favor of the following recursive logic:

• If I'm a call frame with an empty node, the depth is 0 so return 0
• Otherwise, return 1 for my node plus the larger of whatever values my children have.

That's it!

By the way, adding the result as a parameter isn't just a "that's cool, less code, whatever, maybe I like being verbose" thing -- you can actually wreck your memoization attempt with it on dynamic programming problems, so it's quite critical to be clear about what the dependencies are in the DAG of problems you're solving.

Here's a concrete example of this sort of thing messing things up in real life over on Stack Overflow: Issue with memoization - House Robber problem.

---

So, to summarize how to avoid these recursive antipatterns:

• Try not to touch child properties anywhere except to set up your recursive calls
• Generally don't use parameters as return values

If it seems over-complicated, it probably is.