# Leetcode 104 — Maximum Depth of Binary Tree

This article will cover and explain 2 solutions to Leetcode 104, Maximum Depth of Binary Tree.

# Problem Overview

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.

Constraints:

The number of nodes in the tree is in the range `[0, 10^4]`

`-100 <= Node.val <= 100`

Questions you may have are

• What are the node class properties/methods? Answer:
`// Remember the class name as it's referenced in the solutionsclass TreeNode:    def __init__(self, val=0, left=None, right=None):        self.val = val        self.left = left        self.right = right`
• What to output if the input root is null? Answer: `0`

# Example

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

Don’t worry about the input being an array, it is translated into a graph before it gets to us. The maximum depth is 3 because there are 3 depths, or layers, to this tree. Those depths are highlighted in green, orange, and blue above, with their depth called out on the right.

So, at it’s core this problem deals with strategies of how to traverse a tree structure. In this article I’ll cover a recursive Depth First Search (DFS), and an iterative Breadth First Search (BFS) and Depth First Search (DFS). Beginning with the recursive DFS, I want to introduce the solution then visualize why it works.

# Recursive Solution (DFS)

It’s a short solution, and to a beginner it may seem a bit confusing. So, I’m going to visualize why this works in the following depiction:

Taking it from the top left:

1. We have `root` which is NOT `None` and so we recurse with `root.left, root.right` . Beginning first by evaluating `self.maxDepth(root.left) == self.maxDepth(9)` , which turns out to return `1` because node ‘9’ is a leaf node.
2. So `1` was returned from `self.maxDepth(9.left)` and now we evaluate the right side of node ‘9’, which is also `self.maxDepth(None)`
3. We see here that we evaluate that expression to be 1.
4. Lastly, we’ve returned to `self.maxDepth(9)` which can now return `1+max(1, 1)` to our original statement from root.

# Iterative Solutions

There are 2 simple iterative solutions. The first I’ll show is a simple one using a stack (a DFS solution):

How does this work?

1. Begin with adding `root` to a list (that acts as a stack) along with it’s depth. Track the `maxDepth` observed. And enter our while loop.
2. Pop the top element of the list which is a pair of `node, depth of node` . It’s important that this is a pair because 1) We need the node (obvious) and 2) We need to know the depth the node was observed at.
3. Compare it’s `depth` to `maxDepth` , so that our return value is being tracked and updated.
4. Add all of `node`'s children to the stack (the DFS is that we iterate down all the children before backtracking up).
5. Repeat 2–4 until the while condition breaks

The iterative BFS (or level order) solution may be a bit harder to follow. It utilizes the same principles of visiting a node, adding it’s children to a list, and repeating. However, the difference is here we utilize a double ended que as a FIFO. Meaning, we add all the children for a node, and don’t advance to another depth in the tree until we’ve visited (added) all the children added.

The tricky thing here could be understanding that the algorithm does NOT traverse to a new depth until all child nodes at the current depth have been visited. That behavior is dictated by 2 things:

1. The use of a FIFO queue instead of a LIFO. So, all the child nodes added first are also all the nodes visited first (see `dque.popleft()` ).
2. Tracking the children at the current depth that remain to be visited with `nodes_at_curr_depth` .

I hope you enjoyed the article! Leave a clap if you want to see more :) !

--

-- ## Thomas Higginson

Software Engineer working on Cognitive EW capabilities, and human that enjoys making smiles. Welcome.