Crack Leetcode 104: Maximum Depth of Binary Tree

There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 140 — maximum depth of binary tree — together. After this article, you’ll learn 3 solutions: Recursion, BFS(Breath-First-Search), and DFS(Depth-First-Search). Without further ado, let’s get started.

Problem Description:

Image for post
Image for post
(Image captured from Leetcode : https://leetcode.com/problems/maximum-depth-of-binary-tree/ )

Solution #1: Recursion

Explain the idea:

The naïve idea is like this: Given the tree root node, if somehow we know the maxDepth of left subtree, and the maxDepth of right subtree, then we just need to compare the two values, and return (the larger one + 1).

Image for post
Image for post

Pseudo code:

And that “somehow” can be solved by recursion. Assume a function called “maxDepth” can return the max depth of a tree. We recursively call the function itself until it reaches the base case. The base case is when the input tree root node is [ ], meaning root == None, and we return 0.

Image for post
Image for post

Python code:

So the python code is like this:

Image for post
Image for post

Solution #2: BFS

Explain the idea:

We see many levels in the tree. If we know how many levels are there, we then know the max depth of the tree.

Image for post
Image for post

If we go through all the nodes in level 1, and then go through all the nodes in level 2, so on and so forth to the end, this is what’s called “Breath-First-Search” (BFS).

Image for post
Image for post

And this is achieved with queue. Queue is like a funnel: who comes in first goes out first (First-In-First-Out, FIFO).

How to use queue here? First we put (depth=1, tree root node) into an empty queue.

Image for post
Image for post

Then pop it out, put its children in, and then increase depth by one. Let’s understand it with this image:

Image for post
Image for post

Again, we pop node2 out, and put its children in, increase depth by one:

Image for post
Image for post

keep doing this until the queue is empty:

Image for post
Image for post
————————————
Image for post
Image for post

When the queue is empty, the depth is 4. So the max depth of this tree is 4.

Python code:

The python code is like this:

Image for post
Image for post

Solution #3: DFS

If we can somehow find all the paths from root to leaf (i.e. a node with no children), then we can compare their lengths and return the largest value.

Image for post
Image for post

This happened to be another way to go over every node in a tree, which is called “Depth-First-Search” (DFS).

DFS is realized by stack. Stack is like a tennis-ball bottle, what comes in last goes out first (Last-In-First-Out, LIFO), because it has only one outlet, and that’s what makes it different than Queue.

So how do we use stack here? First we put (depth=1, tree root node) into an empty stack.

Image for post
Image for post

Then pop it out, put its children in, and then increase depth by one. Let’s understand it with this image:

Image for post
Image for post

and then pop node 2 out, put its children in, increase depth by one:

Image for post
Image for post

repeat this process, until the popped out node has no children. Then we put its depth into our DepthList:

Image for post
Image for post
————————————
Image for post
Image for post
————————————
Image for post
Image for post

Now the stack is empty. And then we check the DepthList. The largest value is the maximum depth of the tree.

Python code:

The python code is like this:

Image for post
Image for post

The End

Since it’s already so looong, I won’t jump into details for Time and Space complexity analysis. Instead, this is your little homework ;)

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store