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:
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).
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.
Python code:
So the python code is like this:
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.
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).
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.
Then pop it out, put its children in, and then increase depth by one. Let’s understand it with this image:
Again, we pop node2 out, and put its children in, increase depth by one:
keep doing this until the queue is empty:
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:
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.
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.
Then pop it out, put its children in, and then increase depth by one. Let’s understand it with this image:
and then pop node 2 out, put its children in, increase depth by one:
repeat this process, until the popped out node has no children. Then we put its depth into our DepthList:
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:
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!
