Repeat Code With LeetCode — Maximum Depth Of Binary Tree
Another meme problem
You got this. You solved eight easy LeetCode questions, and you even bought Cracking The Coding Interview but didn’t read it.
— Source hyping himself up before a coding interview
Tree problems can be a bit tricky, but this one is a LeetCode easy. Kevin Naughton Jr. and Nick White both have different explanations of the same solution, but I find Kevin’s a lot more intuitive.
There are two ways to solve this problem. Both are more or less straightforward — you don’t really need a “clever” trick, but this one can be called the cleverer of the two.
Kevin explains it well. Imagine you are going to a movie theater alone, because having friends or a significant other would break the metaphor. You want to know how many rows there are ahead of you (ie what row you are in). The movie theater is dark, but you have the ability to tap the shoulder and talk to the two people in front of you.
This is a recursive call. Each person will, in turn, have the ability to tap the shoulders of the people in front of them. The base case for your recursive call is when a person (child node) does not have anyone in front because he/she is in the first row.
You can only talk to the two people in front of you, but by using recursion you have empowered these two people to obtain knowledge for the entire tree.
The metaphor makes less sense the more you think about it (what, do you not have a ticket?), but on the surface it very quickly sums up:
- How we can use a depth first search (DFS) to solve this problem
- How a recursive function makes a call to itself
- How a recursive function only works if there is a base case
Add 1 to the maximum of a DFS to the left and a DFS to the right.
The Problem
Maximum depth of a binary tree
Difficulty: Easy
Skills Required: DFS (depending on implementation)
Description:
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 Solution
No one else seemed to make the dfs a helper function, but I wrote it that way out of habit. Note that this is a recursive function because dfs has a base case (null root), and because dfs calls dfs.
If you have seen tree problems in C++ before, then the above should look pretty familiar. If you have not, and you find it confusing, that is okay.
This is a bit language-specific, but the comment in lines 1–10 is just how LeetCode defines virtually ALL of its tree problems. You have a struct for your TreeNode — you don’t have to bother defining one yourself. A TreeNode has a value (which is just a number, even though a real tree can store something else), a reference to a left TreeNode (may be null), and a reference to the right TreeNode. We are using arrows in C++ because it’s a short-hand way to access the pointer values. In other programming languages, the concept is the same.
A lot of DFS functions read the same way. What I wrote in lines 14–22 is a pretty typical use of DFS, though returning the maximum is specific to this problem.
Recursion could be its own post, but I hope it’s not too confusing that to be a recursive function, dfs calls dfs. Without a base case, recursion is an infinite disaster (as made famous by a Sesame Street video).
With a base case, recursion is a neat trick. Any “base case tree node” resolves, which allows the call to that tree node to resolve. Every happy, resolved tree node can pass its calculation to its caller, and now the caller tree nodes are satisfied. Every tree node becomes something like a neuron, messaging its calculation up until the final answer reaches you (the original caller). Now you get to see how deep the tree goes.
