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 creating intermediate variables for conditions:

  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've made these mistakes too and still do!).

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, 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. If you find you have to, then you may have formulated the problem incorrectly or recursion may not the correct pattern to apply to the problem.

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, any given piece of data flows one way: results flow back up the tree and state flows down.

If you're passing the same data representing the results down and then back up again 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 an issue of reducing verbosity (although that's reason enough for me) -- 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. If it's not a dependency (i.e. it's a result, or irrelevant information), then it has to be taken out of the memoization table.

Here's a concrete example of this over on Stack Overflow: Issue with memoization - House Robber problem. If you haven't done DP yet, no problem -- the point is that adding complexity is usually worse than an aesthetics issue.

---

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 the solution seems over-complicated, it probably is.