Welcome back, everyone.
So I know we just learned a bunch of little topics inside of binary trees that seem a little bit daunting,
especially around how they get incorporated in our technical interviews.
Now, binary trees is definitely one of the more complex data structures.
And there are a lot of variations of questions that show up in binary trees because there are so many
little topics that can be added for that complexity with our questions.
But in this section, I'm going to show you a very solid approach that you can apply to solving these
binary tree questions.
We're going to tackle all the topics that can get incorporated into a binary tree that we just learned
in our appendix from full versus complete trees, the different kinds of traversal, breath versus depth,
first search and binary trees versus binary search trees.
But the best place to begin is to focus on just binary trees and not add the complexity of binary search
trees yet.
So with binary trees, there are two reversals and there are search types.
We already know there's breadth, first search and depth, first search, as well as preorder in order
and post order traversal.
These five main topics all revolve around navigating through a binary tree.
The key with this is trying to figure out which of these five tools you can bring into your solution
so it can help you actually execute the logical solution you come up with for your question.
And we're going to explore all this, if that seems a little confusing.
But I want you to keep that in mind.
These are the tools that will best help you implement your solution when it comes to navigating through
your binary tree.
And we're going to start with a very easy binary tree question just to get familiar with this exact
navigation.
So the question is going to say, given a binary tree, find its maximum depth here.
A maximum depth is defined as the number of nodes along the longest path from the root node to the furthest
leaf node.
So when we look at this, let's say we were given this binary tree structure, we want to find the maximum
path, which is defined as the distance from that root node, which is the green node at the top to
the furthest leaf node, which is that orange node at the bottom.
Here we can see the longest path would be highlighted by these green nodes.
And if we count the number of nodes we see that we end up with five.
So the answer here that we would return if given this binary tree structure is five, because the five
nodes highlighted in green is the maximum depth or the longest path.
So with this in mind, let's solve our question, and the first step, as we always do, is we need
to verify the constraints.
So this question is pretty straightforward.
So there really aren't that many constraints for us to ask about one.
What we can ask for our own measure is what do we return?
If the tree is empty, if the tree is empty, we just return zero because maximum depth here will be
zero.
Similarily, if we receive a tree where there's just one node, which is the root node, we can return
one because that is still the depth of one.
This question is not as complex because we are just returning the maximum depth, which is a number,
we're not returning the path itself, which means that if there are multiple branches that time for
the same maximum depth, we don't have to return either of those as our consideration.
All we have to return is the maximum depth number, which is what makes this question really easy and
straightforward.
So from here on, we can move on to the next step, which is to write out some test cases.
When coming up with test cases for binary tree questions, you want the best case, you want the null
cases, but there's actually one additional case you want to consider, which is considered a worst
case.
And I'll show you what that looks like.
So here with our best case, we're just going to duplicate that tree we saw when we first explored this
question.
So with this example, this tree is going to have no values inside of the tree nuts.
The reason for this is because we don't care about any values inside of our binary tree, as we already
saw.
We're simply looking for the depth of this tree or the maximum depth of the tree.
The values for us do nothing.
And with this one, we count the nodes from this route all the way down to the furthest lymph node,
and we see that this gives us five.
So the answer for this tree is going to be five for our null cases.
We know there's a chance where we get null, meaning that there are no nodes as the binary tree.
In this case, we're going to return zero similarily if we receive just a single node, which is going
to be just the root node with no children.
We want to return one.
So this is the three cases we have our best case, we have our null cases or our single case, but we
also have that worst case now.
The worst case scenario for any binary tree that we generally should consider is one where we have all
of the nodes that sit along one path.
So here I'm just going to write this in and fill out that left side as null.
But what you'll notice is that in order to traverse down any of these nodes, you're going to follow
along the path.
This is significant because when it comes to your space and time complexity, it's always going to be
out of end because worst case, if you need to reach this node, you're going to have to go through
the entire tree.
And this is going to impact both space and time complexity.
And I'll show you when we actually explore solutions for this question.
But in this case, we know that this answer is going to be five because the first node is five notes
down.
But this, again, is mainly just an impact on space and time, complexity considerations.
So now that we have our test cases, I want you to try and come up with a solution yourself.
So take our best case test case and consider our worst cases as well and see if you can think of a logical
solution.
It might be difficult because you don't really know how to apply some of these ideas yet, but it's
still good to see if you can fight with the problem a little bit and come up with anything yourself.
If not, I'm going to show you in the next lesson.
So I'll see you in that lesson.