So in order for us to cut out our solution, I'm just going to reference this pseudocode block that
we had written in our previous lesson.
So here I want to initialize our function, which I'm going to call Max depth.
We also know that this is going to be a recursive function, so I'm going to pass it.
The two arguments we've had to find.
The first is going to be the node.
The next is going to be the current depth that we have calculated thus far.
We also want to do a check here and say that if there is no value for node, so if notis falsey, which
we know that null is falsey, then we just want to return the current depth.
Alternatively, if Noad does have a value, then I want to increment the value of this current depth
by one.
And then the next thing that we're going to do is just return the maximum value of calling our recursion.
So I'm going to say return math, Max, as our second base case.
And here I want to call Max depth on no dot left while passing in current depth.
And similarly, I am going to do the same thing on the right side, I'm just going to do it down here
because we don't have enough room.
So I'm going to call Max Depth on node, right.
Also passing in current depth.
So this is actually almost the exact same as our pseudocode.
But that's our solution.
Very simple.
It's pretty much just exactly what we explored in our pseudocode.
Now, this might not always be the case when you do these binary tree questions that your pseudocode
matches the actual final solution so closely.
The main idea of the pseudocode is to capture the bulk of the logic around how we solve this question.
But luckily for us with this question, it's pretty much the exact same thing.
As always, there is a link to the actual solution if you cannot read the handwriting that I've got
here inside of your resources folder.
But let's analyze the space and time complexity here.
So when we think about time, complexity in a worst case scenario, we can imagine that this binary
tree is flipped.
And yes, while we look at this recursion, we explore the left first.
If this tree was flipped such that this longest path was on the right side instead of on the left side,
then it would be the very last note that we would explore.
What that means is essentially we end up exploring every single node inside of this tree.
So what this means is that our time complexity has a worst case of oh, of and being the total number
of nodes in the tree.
What about space?
Complexity, space?
Complexity is going to be the size of our recursion.
Now, in the example with this binary tree or recursive call can get as large as five because we are
going to traverse five nodes down, which means that we are going to recursively call five different
function calls to get to this last note.
So you can see this as the case where the height of the tree is the size of the recursion.
And in a perfectly balanced tree, the height of the tree is of log ln and being the number of notes.
If you don't remember why this is the case, we are dividing the number of nodes by two in order to
fit equal size in the levels.
So in a perfectly balanced, fully complete tree, every single level is filled and in that case, log
in is the height of the tree.
But this is the best case.
What about the worst case?
The worst case is where we consider that tree that I originally showed you, the tree where every single
node sits on the right child of the actual value.
So here when you have a binary tree of this size, what is the height of the tree?
The height of the tree is.
So that's why you have to consider as far as space complexity goes, if we're recursively calling down
every single child of every single node, then our recursive stack is the size of this tree, which
is N.
So the worst case scenario is we receive a skewed tree like this and we have O of NP as the space complexity.
So space you want to consider worst case scenario of end.
And this is our solution.
This is generally the best solution you can get.
And the reason why we are able to get to this best case solution right away is because of the way that
we concern ourselves with how to solve this question.
Generally speaking, you can with binary tree questions half the time, get straight to the proper solution
when you consider all of the cases of what you need to apply here, which is search type and traversal
type here at this point with a lot of our recursive solutions in order to practice, we want to go straight
for maybe the optimal solution.
If it's obvious to us that the steps we take to get there will help us get to the solution.
So you'll notice with some of these questions that we do, we're not going to come up with a brute force
solution first, because sometimes the brute force solution doesn't actually get us to the optimal solution.
So it's really going to be something that comes to you with more practice of these questions, which
we are going to do.
So now that we have a general basic idea of how to tackle some binary tree questions, let's keep practicing
with another question.