Binary Tree Algorithms for Technical Interviews - Full Course
Binary Tree Algorithms for Technical Interviews - Full Course
Learn how to implement binary tree algorithms and how to use them to solve coding challenges. 🌳
✏️ This course was developed by Alvin Zablan from Structy. Check out Alvin’s channel: / alvintheprogrammer
🔗 Learn data structures and algorithms: https://structy.net/
⭐️ Course Contents ⭐️
⌨️ (0:00:00) Course Introduction
⌨️ (0:01:09) What is a Binary Tree?
⌨️ (0:11:28) Binary Tree Node Class
⌨️ (0:14:19) Depth First Values - (https://structy.net/problems/depth-fi…)
⌨️ (0:36:00) Breadth First Values - (https://structy.net/problems/breadth-…)
⌨️ (0:47:43) Tree Includes - (https://structy.net/problems/tree-inc…)
⌨️ (1:05:35) Tree Sum - (https://structy.net/problems/tree-sum)
⌨️ (1:19:53) Tree Min Value - (https://structy.net/problems/tree-min…)
⌨️ (1:34:16) Max Root to Leaf Path Sum - (https://structy.net/problems/max-root…)
⌨️ (1:48:28) Conclusion
🎉 Thanks to our Champion and Sponsor supporters:
👾 Wong Voon jinq
👾 hexploitation
👾 Katia Moran
👾 BlckPhantom
👾 Nick Raker
👾 Otis Morgan
👾 DeezMaster
👾 AppWrite
—
Learn to code for free and get a developer job: https://www.freecodecamp.org
Read hundreds of articles on programming: https://freecodecamp.org/news
Content
0.08 -> binary tree is a common data structure
used in software development.
4.08 -> It's also a frequent topic and technical coding
interviews in this course, Alvin will explain
8.88 -> binary tree algorithms and prepare you to use
them in both interviews and coding projects.
16.88 -> Hey programmers, Hamilton from Shruthi, elk to
our course on binary trees, I want to show you
21.52 -> how you can do well on those technical interviews
that have binary tree problems. So what I have in
26.56 -> store for this course, like usual, we'll go over
both the theory pines and binary tree algorithms,
31.04 -> as well as of course be more practical and come
up with a code implement those algorithms really
36 -> a one two punch. For every section, we're going to
be sure to draw out a pictures and visualize and
40 -> truly understand the algorithm on the whiteboard
notes are feeling comfortable with that,
43.68 -> we'll go over to the code implementation.
So in the description and in the timestamps,
47.68 -> you'll be able to find the corresponding exercise,
you can practice every algorithm that we go over.
53.36 -> In terms of the prerequisites for this
course, I'm going to assume that you're
56.48 -> not new to programming. And maybe you've dabbled
in some previous data structures and algorithms.
60.72 -> And you're also familiar with some recursion.
But that being said, I'm going to assume you know
64.64 -> nothing about binary trees, and even just trees in
general. with no further ado, let's jump right in.
71.12 -> So first order of businesses, let's actually
understand what the word tree even means. And
75.12 -> like the programming concept, right. So when we
visualize a tree, a tree contains many nodes,
80.56 -> typically we draw nodes as circles, right. And
these nodes can also point to other nodes. So
85.76 -> here I have one node. And I could point to some
other node, right, I could point to any number of
91.04 -> nodes. So here are the circles, I'm going to refer
to them as nodes, and the lines or hours between
95.76 -> them, I'm going to call edges, right. So this is
an example of a tree. And trees can of course,
101.28 -> come in many different shapes and sizes. So here's
quite a large tree. Let's try to understand a few
106.4 -> terms we can use during our technical interviews.
And this is something I highly recommend, right?
110.72 -> helps if you speak the language, it does show
that you have proficiency dealing with the data
114.64 -> structure, we could store values within the nodes
of our tree. For now I'm just going to put some
119.6 -> letters. When it comes to your programs, you can
store any type you want, you can store integers,
124.08 -> numbers, or even other objects. So because we have
a tree, we like to use familial relationships. In
129.84 -> other words, I think of like a family tree, right?
So if I look at node B, let's say I call them the
135.28 -> parent. If b is the parent, I know that children
of B are just the D nodes, right? their parent
141.52 -> and child is like a relative relationship. Let's
say I kind of changed my frame of reference. And
146.16 -> let's say I looked at a as the parent, well, that
scenario, then B and C are the children of a. for
152.88 -> the case of the C node, if I think of CSM parent,
it only has one child, its lone child being the F
158.72 -> node. So feel free to use that parent child
relationship when describing the relationship
163.12 -> among nodes within a tree. Another terminal is
a lot in the context of trees is the word root,
169.52 -> right? So a root is going to be a node that has no
parent. So in this tree, A is the root because a
176.8 -> has no parent, right? There are no arrows going
into the a node. On the flip side of that,
182.8 -> if I look at the nodes in DNF, we call
them leaf nodes. A leaf node is a node
188.08 -> that has no children, right, so d and f have no
outgoing arrows. Typically, in a binary tree,
193.92 -> we're going to have a single root and we could
have many leaves. One thing I want to be sure to
198.64 -> do is make sure you generalize your understanding
of a leaf, right? So in this particular example,
203.04 -> looks like every leaf is two edges away from
the root, counting the number of arrows from
207.6 -> the roots, any leaf, it could be the case that
my leaves occur at different levels, right? So
212.4 -> I removed that F node, which case C is now a leaf,
right? Although a C is on like a different level
218.72 -> than D and E, it's not the bottommost level, it
is the case that it's still a leaf, right? a leaf
222.88 -> node is just a node that has zero children. All
right. So with all of those terms out of the way,
228.88 -> let's hone in on the real topic here. Right,
I talked a lot about trees. But really in this
232.8 -> course, I want to go over the basics of binary
trees. Right? So let's look at that binary part
238.16 -> to begin with. That's really a dead giveaway.
We know binary has to do with the number two.
242.72 -> A binary tree is a tree where every node has at
most two children. Right? So currently on the
249.28 -> screen, I have a binary tree. If I gave a another
child, let's say a third node over here of f,
255.68 -> this would be a tree but not a binary tree. Right?
It would be like a ternary tree because I have at
260.8 -> most three children. So let's say I kind of remove
that extra node. Now it's back to a binary tree.
267.28 -> And it could be the case that a node has less
than two children but still be a binary tree,
271.84 -> right? So if I gave C, just a child of f, this is
still a binary tree. It's if I look at any node
278.48 -> within my tree, that node will have 01 or two
children, and no one has more than two children,
284.48 -> right? So you want to be sure to remember that
a node in a binary tree could have less than
288.48 -> two children. All right. So I'll be the first
criteria for understanding what a binary tree
293.36 -> is right? It's probably the easiest criteria and
most children per node will also want to be sure
298.8 -> to add into our definition Have a robust
understanding is to also remember that,
302.64 -> at least for us in computer science, we think
of our binary trees as having exactly one root,
308 -> meaning there should be only a single node that
has no parent, right? Typically when we draw,
313.12 -> it would be like the topmost node. So right
now this is definitely so far a binary tree.
318.8 -> If I had some other node in this drawing,
like G, right, g also has no parents,
323.44 -> I would no longer consider this a classic
binary tree, right? So watch out for that.
329.6 -> Let's go on to our final criteria, we also need
one more ingredient. And that's exactly one path
334.8 -> between the root and any node, right. So looking
at my example to the left, this is indeed a binary
340.24 -> tree that meets all three criteria. And let's say
I chose the root and any node, obviously, there's
345.12 -> only one root, so we're definitely considering the
a node, let's say I chose some random node like E,
349.84 -> this is really a binary tree, then we're
guaranteed to have only a single path that
353.6 -> connects A to E, a path is really just a series
of connected nodes I can travel through, right,
359.36 -> so to get from the root a to the node E, I
can go from A to B to E, and that would be
365.28 -> one path. And that's the only way to get from
A to E. That's what I mean by exactly one path.
370.72 -> Let's say I chose another node like F. There is
also exactly one way to get from the root to F,
375.84 -> and that's just a CF, that would be the only path.
If I added some additional connections or edges
381.84 -> within my tree, I can get a scenario like this,
this would no longer be a binary tree. For one,
388.8 -> we can see that B has three children, but also
does not have a unique path between the route
393.44 -> in any node. For example, if I chose a and the
note of f, one way to get there is by going ACF.
400.24 -> But another way to get there would be a, b, c, f,
right? And so do watch out for all three criteria
406.8 -> when you're considering a binary tree. Awesome. So
let's look at some smaller examples. And this is
412.24 -> where I think some students tend to struggle with
their understanding of binary trees. So if I took
416.48 -> out some nodes over here, this would definitely
still be a binary tree, right? Just looking at our
420.56 -> different rules, right? Let's say the root node A
only had one child would still be a binary tree,
427.52 -> right? Because the binary tree only demands that
we have at most two children, we still have one
432.16 -> root, and we still have only one path from root
to any node. Let's say I have the smallest tree
438.08 -> that has a node, which would be the singleton
tree, this is still considered a binary tree,
443.6 -> right has one route. And there's not really any
pass to be had here except the route to itself.
448.08 -> And every node does have at most two
children. Here we have zero children, right?
452.24 -> The final edge case we want to think about
is what happens when we have no nodes,
456.4 -> right? We consider this as the empty tree. This
is a very special case. And we should consider
462.16 -> any empty tree as actually being a binary tree.
That's going to be very useful when we come up
467.36 -> with some algorithms later on, right. So a common
edge case off to consider is what happens when we
471.76 -> have an empty tree, that's a tree with zero
nodes, right? Let's look at another example.
477.12 -> Let's say I had this structure to take a moment
look at it, and see if this meets our criteria.
483.84 -> This would not be considered a binary tree. So
we look at your different criteria. Looking at
488.96 -> the first one, it does have at most two children
per node, so that's okay. But we can't identify
494 -> exactly one root here. Remember that a root
node is a node that has no parent, right?
499.36 -> If you look at every node in this picture, every
node has exactly one ingoing arrow. So that means
505.52 -> every node has at least one parent,
right? So it doesn't meet that criteria.
509.92 -> And furthermore, there is not exactly
one path between the root and any node,
513.84 -> because we have a cycle within the structure.
So for example, let's say I was starting at a
519.84 -> right and I wanted to travel to see, one
way to get there would be to go A, B, C,
525.2 -> that'd be one path. But I could also have another
path or I just go around twice and go A, B, C,
531.36 -> again, there would actually be an infinite number
of paths in this scenario. Because of that, this
536.16 -> is definitely not a binary tree. And there kind
of many reasons for that. If I had a different
540.24 -> example, looking at this one, now I need criteria
one and two, right, I have at most two children
545.68 -> for every node. But I also still have exactly
one root node here I would consider z the root
550.08 -> node. However, there is not one path between the
roots in any node and because I have that cycle.
556.24 -> So these rules are really worth remembering,
they're really going to help you solve a much
559.52 -> more difficult binary tree problems. And if you
remember these three rules, you can identify
565.52 -> different problems in a binary tree framework.
In other words, the hardest problems that you'll
570.16 -> encounter in your interviews are problems
where they don't tell you straight up what
573.92 -> data structure you're dealing with, you're just
gonna have to notice the pattern. In other words,
578 -> what if I gave you some structure like this, take
a moment and figure out if this is a binary tree.
585.68 -> If you look closely, this does meet all
of the three criteria to be a binary tree.
590.24 -> I can just treat a as the root because it has no
parent. I can treat nodes D and F as the leaves
596.08 -> because they have no children. I just drew
this in a pretty interesting way. Right? If
599.6 -> you really range things in a classical binary tree
sense would look like this. More importantly, this
604.88 -> has the same relationships as a previous drawing,
I just show it in a top down fashion, right? So no
610.48 -> matter what do you understand these three rules
for a binary tree, right? Because sometimes may
615.12 -> not be as explicit as a nice triangular shaped
drawing. Awesome. So we've talked a lot about the
620.08 -> theory of how to, you know, look at and reason
through some binary tree definitions. Let's
624.4 -> go ahead and start to talk about how we could
represent binary tree programmatically. In other
628.4 -> words, how can we do this in some code? Well,
no matter your programming language of choice,
632.64 -> I think you're going to represent these as
objects. In other words, every node here is
636.48 -> going to be some objects. So it could be like an
instance of a class, the properties only to store
641.6 -> within this object would be the current value. So
I need something to store like the A of my current
645.76 -> node. But I also need to refer to some children.
So we'll also need some left and right pointers
651.6 -> to the children, right, those are just going to
be some properties on that object. In a classic
657.28 -> binary tree is very common to refer to the
two children using a left and right direction.
661.92 -> Notice that some nodes here, like the C node,
they're only going to have one child, right? c
666.96 -> only has a node dot, right? It does not have a
left. So we're gonna have to use some empty value,
671.84 -> like null or undefined. To represent a child that
doesn't exist, right? Especially for a node like
678.48 -> he, he has no left and also no, right. So here's
what we'll do, let's go ahead and hop into my text
684.48 -> editor. And I'll show you how you could represent
a binary tree programmatically. So transition,
689.6 -> here we are in my text editor. Let's start by
creating our node class, right. So you'll be able
694.32 -> to follow along any language that you choose,
I'm going to do mine in JavaScript, right. So
698.88 -> I think the best way to present a node is just
to use some class. So hopefully familiar with
703.04 -> some classic class syntax, let's create a node
class, there's going to be a quick constructor,
709.92 -> I think would be valuable to take in the initial
value that's going to be stored within the notes,
714.48 -> I'll take the ns a constructor argument, I can
just set this dot Val to that value, and also need
719.92 -> two more properties, one for my left, so I can say
this dot left, I'm gonna initialize it to null,
725.52 -> that means by default, a node will have no left
child the same way. By default, a node will have
732 -> no right child, right? So when you use no to
represent children that don't exist over here,
738 -> awesome. That's all you need to create, you know,
a baseline binary tree, right, we're going to use
742.72 -> this class a lot during the course to test our
algorithms. So I'm going to create a node and
747.36 -> eventually wire up a tree. Well, I'll just call
my constructor few times, I'll create different
751.44 -> nodes, I'll just store them to some variable
names. And of course, a new node to create
755.28 -> new instance of node, and I'll store some value
inside, I'm going to store some characters inside,
759.76 -> I'll create a bunch of these different nodes,
what we'll want to be sure to do is make sure
765.12 -> that you also set their pointers properly. So
I'll give each of these some different values ABC,
770.96 -> D, E, also do F. And then I'll just manually
for now set their pointers properly.
779.2 -> So what if I did syntax like this is since I'm in
JavaScript, I can easily assign these pointers,
783.84 -> I can say, A's left is going to be B. I can
say A's right? is C can also say B's left D.
793.6 -> and then B's right is E. And maybe Finally I can
say C's right is F. So by doing these assignments,
802.24 -> I'm connecting some nodes together, I should
end up with a structure like this right? Have
807.76 -> a as a root, because nothing points to a
it has no parent. But a has two children
813.28 -> of the NC. And then along with
that, B has two children of D and E.
822.24 -> Finally, C just has a right child of f, this is
actually the same tree that we looked at a lot
828.72 -> during the whiteboard session, right? And
that's how you can represent that same tree
832.56 -> programmatically, right? So I always think it's
valuable to also try to visualize your trees,
836.88 -> right? Obviously, we created this tree in a very
manual way, probably in the long run will create
840.96 -> applications to just maintain and create trees
dynamically during some input. But for now,
846.48 -> we'll start by creating all of our
trees in this very kind of static way.
849.92 -> Right? And so with that, now that we have an
understanding of how to represent a binary tree,
855.28 -> let's go head back to the whiteboard. And
I can show us our very first algorithm.
862.72 -> Hey, programmers, Alvin here, right? Now I want
to go over this depth first values problem.
867.04 -> So this will be a good review of the depth first
traversal algorithm. So what do you want to do in
871.76 -> this problem? Well, what we want to do is take in
a binary tree, and in particular, your function is
877.12 -> going to take in the root of the binary tree.
And just recall that given the root node of a
882.08 -> binary tree, we know that that node is going to
have pointers to its left and right children,
886.8 -> which may point to other nodes. However, if let's
say a node does not have left or right child, then
892.8 -> its point is going to be set to No. So that's how
I represent our binary tree programmatically. But
897.84 -> for now, let's just stick to the visual represent
of our tree. So for a depth first traversal,
902.72 -> we could start with the root node of a, what we'll
do is we'll just add that to some collection.
907.92 -> And we're going to have to maintain these in
a very particular order. And then from there,
911.6 -> according to a depth first traversal, I could
go to B. And here's where we make our really
916.08 -> important decision, right, we can either go to
C, or D, if I'm doing a depth first traversal,
921.92 -> I need to go deeper in the tree before I move
laterally. So that means I go from B to D.
928.56 -> And once I bought them out at D, there's
nowhere deeper, I can go from D. And so now
933.2 -> I move laterally to the E node. And this pattern
continues, right? I don't have anything deeper
938.56 -> from E. So now I go to C. And then from C, I go
to f. So this would be a depth first traversal
944.64 -> on this binary tree. Notice that it goes A,
B, D, E, C, F, and again, the really important
949.6 -> characteristic is we must go deeper in the tree
until we can't anymore and then we can go across
955.76 -> the tree. That being said, How can we actually
managed to implement this algorithm. If you're
961.28 -> familiar with depth first, traditionally, then we
know that it's going to use a data structure like
965.52 -> a stack. So let's get situated over here. So we'll
trace through that again. But this time, taking
971.04 -> a really close look at how we can use a stack to
accomplish that direct order. And so just recall
976.56 -> that a stack is a sequential data structure where
we can only add things to the top of the stack
981.52 -> and remove things from the top of the stack.
So a really important characteristic is
985.52 -> we can't really insert or remove elements from
anywhere but the top of the stack. So when I add
991.44 -> things to the stack, I was added to the top like
this. When I remove things, it's also from the top
996.88 -> like this. Alright, so when I begin at this
depth first traversal algorithm, I'm going to
1002.64 -> start with the root node of a. And by default, I
really just take that root node and I just store
1008.64 -> it on my stack. So it's the only thing on my stack
right now, I'll use these rectangles represent my
1013.6 -> different stack frames. And really in my program,
that would just mean storing the actual instance
1018.56 -> of node or some pointer to it. Cool. And then
from there, I actually begin my main algorithm.
1024.72 -> So the main flow of a depth first traversal, we'll
check if the stack is empty. Right now the stack
1030.64 -> is not empty, because I have at least one element.
And so what I do is I start by removing or popping
1036.88 -> the top element of my stack. So I'm gonna remove
the A, and I'll label that as my current node
1042.56 -> being explored. And when something leaves the
stack, then I can consider it being visited right
1048 -> now. So I need to list out my values, because
that's the whole point of this problem, right?
1051.76 -> So by now I've just visited the a node. At this
point, I can look at that nodes children now.
1056.72 -> So I look at the a node in the tree, and I see
that it has a B child on its left and a C child on
1062.16 -> its right. And from there, I push or add those two
children to my stack. So I'm going to put c first,
1069.04 -> and I put B afterwards. And notice if I push my
right child first, followed by my left child,
1076.24 -> that makes it such that my left child is
at the top of my stack, which means that
1080.16 -> I would hit them next. And that actually ends on
my first iteration of this depth first traversal.
1087.04 -> And now I asked that same question is my stack
empty, it's not. So I removed the top of my stack,
1092.4 -> I'll call it B, my current, which means I could
print it out or insert it into my values list.
1097.76 -> Nice. From there, I consider B's children,
B has two children. So I add them both,
1102.48 -> I push E, followed by pushing D. That ends that
iteration. Now something interesting happens,
1110.08 -> my stack is still not empty. So I know I removed
the top, so I call D, my current, I add D to my
1115.28 -> list of values. But if I look at these children,
it actually has no children, right, and so there's
1121.36 -> nothing to add to the stack from here. And
so technically, I finished this iteration.
1127.76 -> And now I still have stuff on my stack. So now
I pop he off the top of my stack. Same thing
1132.24 -> as before, right, I add to my values, he has
no children. So I'm done with that iteration.
1137.92 -> Finally FC, I removed C from the stack, and I
printed out in my values. And then at this point,
1143.2 -> I see that the C node only has one child, so I'm
just going to push the children that exists so I
1148.32 -> would push the F node onto my stack. And that's
a really important thing to remember when it
1153.84 -> comes to implementing your depth first traversal
you're going to have to check if your children
1157.84 -> exist before you add them to your stack. And now
on the final final iteration, we have the F node
1163.92 -> we remove it from the stack, we add it to our
list of values f has no children. And so I finish
1169.6 -> this iteration and now my stack is empty and I
will just exit right once the stack is empty. I
1175.36 -> know that I must have traveled through the entire
binary tree. So there we have it and we do get the
1180.72 -> correct output over here. So just by using a stack
and just obeying the rules of the stack, that is
1186.48 -> we got pushed to the top and removed from the top
we will get the correct order. important thing to
1191.04 -> remember is you should add your values into your
like values list whenever something leaves the
1198.72 -> stack. That being said, What can we say about the
time and space complexity of this algorithm? Well,
1204.64 -> it's actually pretty straightforward. Let's say
we define n as the number of nodes in this binary
1210.8 -> tree, then we can say that the time complexity of
this is O of n. And why do I say that? Well, we're
1216.4 -> just going to add that every node eventually to
our stack. And that nodes also going to leave the
1221.2 -> stack exactly once. So it's not like we're double
visiting any of the nodes. So I'm guaranteed to
1227.28 -> just run in O of n steps. In a similar way, we
can see that the space complexity is O of n,
1232.8 -> the only thing we stored was really the
stack, which is a linear data structure.
1237.52 -> And we know that we're not going to put ever
more than n things on the stack. So overall,
1242.32 -> we have a linear time and space solution for
this depth first traversal problem. All right,
1247.04 -> I think we have a good understanding about the
approach for a depth first traversal. Now let's
1251.44 -> go ahead to the walkthrough video. And we'll
implement this one in a few ways together. Hey,
1257.68 -> programmers, Alvin here, right. And I want to go
over a JavaScript solution for this depth first
1262 -> values problem. And so we're going to do here is
really just implement that same strategy that we
1266.88 -> traced through in the approach video, pretty much
to the tee. And we'll start with the iterative
1272.48 -> version. And that means of course, we will solve
this one in two different ways, right, we're gonna
1276.72 -> solve it iteratively first, and afterwards,
we'll go ahead and solve it recursively.
1281.6 -> Alright, so let's jump right in over here. Like
we said, in the approach video, we know that the
1286 -> iterative version really relies on us creating a
stack. And for most of your programming languages,
1291.44 -> you can just go ahead and use your like array
data structure for that. So I'm going to use
1295.68 -> just a plain old JavaScript array, I'll go ahead
and name this one stack. And we can just use
1301.44 -> an array to represent a stack as long as we stick
to two particular methods, right, I'm going to use
1306 -> array push, which adds to the end of an array,
and also array pop, which removes from the end
1311.36 -> of the array as well. So I'm going to consider the
end of my array to represent the top of my stack.
1317.6 -> Cool, we'll go ahead and do is initialize
the stack with the root node on top of it.
1324.08 -> Nice, then I can have my main loop for the
algorithm. So we know that we need to keep
1328.08 -> running the algorithm while there's stuff on our
stack. So I can just check while stack dot length
1333.76 -> is greater than zero. So while I have
at least one element on my stack,
1337.92 -> there is some work to be done here. And that will
step through a single iteration of this algorithm,
1343.76 -> we know that we start interation by just
removing the top of our stack, in other words,
1347.76 -> stack dot pop in JavaScript, that will also return
us the element that we just removed. So I'll call
1353.44 -> that my current const current. And that is going
to be an instance of nodes, it's going to be
1360.48 -> one of these objects. Cool. So now that I
remove this element from the top of my stack,
1367.04 -> let's say for now, I just I don't know,
print it out, maybe we'll kind of debug
1371.36 -> this one as we go. So console dot log, current
dot Val, because I know that every instance of
1378.08 -> node has a dot Val prop on the inside. And then
from there, I need to add this nodes children.
1384.16 -> So you might go ahead and guess that to do that,
we could just do stacked up push, I'm going to
1388.72 -> push the left child, one out here, so node or
current dot left, followed by the right child.
1398.48 -> But we also need to make sure that these
children exist, right? Look at the prompt.
1403.12 -> There could be instances, for example,
like this C node over here, this C node
1409.44 -> only has a right child, but has no left child,
right. So what I don't want to do is push C's
1415.2 -> left, because that'd be pushing no onto my
stack, which would give me an error later
1419.76 -> on. Right? So I want to only push the children
if they exist. And I need to individually check
1425.92 -> if the left exists and push it and also if the
right exists and push it, I'm just going to
1430.24 -> add some guard statements for both of these. So
we'll go ahead and insert will say, all right,
1436.08 -> if the current has a left and right side, current
dot left, called justice for the right hand side,
1445.68 -> cool, maybe we can inline this, if you prefer.
Alright, so I'm going to only push the children
1451.12 -> if they exist. And that should actually be the
heart of our depth first algorithm. So we're not
1457.2 -> putting our values inside of an array like the
problem asks, but we should at least be able to
1461.52 -> see the correct order of printing here, because
I'm going to print a nodes value as soon as it
1466.8 -> is removed from my stack. So I'll go ahead and
actually maybe bring in maybe one literal test
1474.24 -> case, so I could just steal this little stub over
here. And this will just print out the values.
1481.76 -> Right, so I'll test this I can hit Run, if
I hit Run, it's just going to execute this
1486.24 -> file just like a script. So it's not
going to run any automatic test cases,
1489.68 -> just going to run my file as is. So if you want
to test it in this way, kind of in a manual way,
1494.4 -> you're gonna have to be sure to call your
function. I do have a console dot log on
1497.68 -> the inside. So I'll just run Run this manually.
And when I do that should see some output here
1505.44 -> looks like node is not defined because I forgot
to bring in my class definition. So I'll do that.
1513.6 -> give that a go. Alright, so looking at our output,
we didn't get our exact depth first traversal,
1519.76 -> like we expected, right? I got ACF, B, D, if
you take a look at what we really printed out,
1525.6 -> we technically did print out a depth first print,
but we favored the right hand side. So we did a,
1532.56 -> c, f, and then B, E, D. So let's say we really
wanted the left to right version of this,
1539.28 -> and all you have to do is flip the order that you
push the children, right, it should be clear by
1544.16 -> looking at these two lines, right? When I add
my children looks like I push the left child,
1549.92 -> and then the right child. If you push the left
child first, and then you push the right child
1556.16 -> afterwards, that means that the right child's
going to be on top for the next iteration. So
1560.72 -> if you do it like this, this will favor the
right hand side and travel through it first.
1564.48 -> But if you did it like this, now you'd be
actually iterating to the left branch first,
1570.64 -> toward the right. So with that small change,
let's just see what our print is. And there
1577.2 -> we have a nice AB de ECF. However, in this
problem, they want us to actually return
1582.48 -> those values in an array. So I can kind of
get rid of this little Manual Test over here,
1587.44 -> I don't need this class definition anymore. And
now instead, I'll just gather up all of my values
1592.8 -> in some results array. So I'll say, maybe result
over here starts as an empty array. And then as I
1599.84 -> pop elements from the top of my stack,
instead of logging them, I'll go ahead and do
1604.8 -> result dot push, and I'll push that value into the
result array. Once I'm done with this while loop,
1610.64 -> that means my entire tree has been explored. which
case I can return, make sure I spell it right,
1616.24 -> return my results. Cool. So this should be a
nice solution, it's actually run the test cases
1622.08 -> on this. give that a go. So it looks like we're
doing pretty good. But for this very last example,
1631.28 -> looks like we're getting can't read property
Val of na, and that's running test case 04.
1637.6 -> So if you actually go into the prompt, those
test cases are actually laid out explicitly
1641.68 -> over here. So I want to go to zero for now
let's look at the zero for test case. They go
1647.68 -> ahead and they pass my function, no, right kind
of representing like an empty tree or an empty
1653.12 -> node. And we can kind of trace it what happens
here for our code. Let's say that root was null.
1660 -> That means when we initialize our stack, our stack
literally contains like a null value. So it's not
1665.92 -> even an instance of note just now. So that means
when I entered this while we're going to check,
1669.84 -> you know, Do I have anything in my stack, and
I do because my stack length is one. And then
1674.8 -> when I pop, the top element of my stack current
is going to be no, then on this line 14 it says
1682.16 -> null dot Val. And that's actually where our
code explodes, right on line 14, right? You
1687.12 -> can't reference property Val, of null. And so
to handle this scenario, we want to make sure
1692.56 -> that we actually never allow anything No, to enter
the stack. It's kind of why we had this guard over
1698.56 -> here. mentioned also be true for even the top
level route, in case they give us the empty tree.
1704.4 -> kind of seems like a corny, you know edge case.
But this is a pretty common one, when you actually
1708.56 -> go into your interviews, right? What
happens if you have an empty input.
1712.4 -> And so I'll just guard that explicitly,
I'll go ahead and check, hey, if my route,
1716.64 -> so if my entire tree is empty. So if route equals
null, then what I'll do is just return an empty
1724.8 -> array, right? Because that means there are no
values inside of it. And that actually is the
1728.72 -> expected answer, according to this, right should
return an empty array. So let's give it a go now
1736.16 -> should be pretty good. Nice. And there,
we have our nice iterative solution for
1741.36 -> this depth first values problem. Alright, so
here's what we'll do. That was one solution.
1747.04 -> Let me show you another way. let's implement
this. And that would be our recursive flavor.
1752.16 -> So I'll just kind of redefine it down below. And
I actually recommend practicing both versions,
1758.96 -> because they're going to serve as like the
basis for which you solve a lot of different
1763.12 -> tree problems. And so when I think about the
recursive version, like all of our recursive code,
1768.56 -> I must think about the simplest case of my
input, and that will act as my base case, right?
1773.12 -> So in the case of a binary tree, the simplest
tree you can be given is going to be the empty
1778 -> tree or just a no root, right? So it's not even
going to be about a node that's single node right
1783.92 -> inside of a binary tree. It's going to be about
an empty tree, right, a tree with zero nodes. I'm
1788.48 -> going to check if my route is no, and I have an
empty tree. And I think about this base case, as
1796.56 -> if it's its own input, because it really is right
and so if someone They asked me to give them back
1801.52 -> in array of all the values in the empty tree, it's
still the case that this must be an empty array,
1807.12 -> right? Because there are no values,
there's even any nodes and the empty tree.
1810.96 -> And then from there, I can generate my actual
recursive call, right. And I know what I call
1818 -> my stuff recursively. That means I have to
reference a function and again, go ahead and
1822 -> invoke it. And I'm going to call upon root dot
left, as well as root dot, right? So this would,
1830.32 -> this call over here would give me back an array
containing all of the values in the left subtree.
1836.24 -> And this will give me an array of all the values
in the right subtree. And so let's say I see these
1841.28 -> into their own variables respectively, you don't
have to do this part. But I'm kind of a fan of it,
1846.08 -> especially if it's the first time implementing
this. So I'll call this my left values.
1851.2 -> I'll call this one my right values. And here's how
I'm able to kind of quickly create recursive codes
1859.12 -> all about taking when I call is a recursive leap
of faith here. So let's say we're stepping through
1866.8 -> test 00. And so this is our tree visual, right?
So we know that our root is going to be a node.
1874.72 -> So when I actually make this top level call,
this base case does not fire. And so I make my
1879.68 -> recursive calls, right? I know when I do depth
first value, or values, rather, let me fix that
1886.32 -> depth first values of root dot left, that means
I'm going to be passing in the B node, right,
1892.48 -> and here's how I have to actually pretend my code
behaves, I'm just going to get back the correct
1898.08 -> result from this call, right? So if I passed
in the B node into this call, what I expect
1904.32 -> back is the full array representing the depth
first traversal of that subtree, starting at B,
1911.36 -> right. So if I got correct data over here,
what it would look like is just B, D, and E.
1919.04 -> That would actually be the full depth
first traversal, from this subtree,
1922 -> right. And I'm kind of doing that just mentally,
or I know the expectation for this algorithm,
1926.72 -> it's going to be a similar story for my right
call, right? If I'm at a So A is still my route,
1932.16 -> and I passed in my right child See,
to this call, what I expect back
1936.96 -> is just an array of CF, which would be the
depth first traversal of that left subtree.
1944.32 -> And now that I have, you know, my left subtree
values and my right subtree values, I have to
1948.4 -> think about how to combine it all together, right?
How do I work myself into that output by combining
1955.28 -> both of the results from my children, right, what
I need to do is really just take myself put it in
1960.48 -> the array, followed by my left children, followed
by my right children. So I can do some nice
1965.84 -> JavaScript syntax for that whenever returning
the right when I throw myself in there, so I'm
1969.92 -> going to throw in a root dot Val, that's myself.
So that'd be like the a node that I just take all
1976.08 -> the values in my left result, put them in here and
just use the spread operator to unpack that array.
1982.48 -> And I'll do the same thing for the right values
of CF, right. So dot dot, dot, spread out right
1987.76 -> values just so I return a single array, and this
pattern itself does match this output, right,
1994.72 -> kind of taking the leap of faith and assuming
correctness from these recursive calls over here,
2000.24 -> right, I have a, and I plug in substitute B, D, E,
and then for the right, I have CF. And even before
2006.96 -> we run this, I'm not going to, you know, assume
too much JavaScript knowledge. So maybe you're
2012.48 -> kind of new to this spread operator. So
in general, super quick aside over here,
2017.04 -> let's say had an array of some stuff. So I'll
say, peeps there and some people over here.
2023.76 -> So we'll throw in fleabay, we'll throw in Jason,
throw in Raj, throw in heavy. And what I can do is
2034.4 -> whenever I have an array, I can just use a spread
operator to kind of unpack that array. So for
2039.52 -> example, I can say const will say new peeps. And
I'll create a new literal array. So whenever I say
2047.52 -> square brackets, it gives me a new array
literal. And what I'll do is, I don't know,
2051.44 -> put an element at the front, we'll call it Alvin.
That'll spread out the elements of peeps, right?
2057.52 -> So just imagine I took all of the elements here
and just remove the brackets. That way I don't add
2062.08 -> any initial nesting. And then at the end, I don't
know I can add someone else. Like, right? Well,
2069.6 -> console dot log, what new peeps looks like so I'm
not gonna run the test cases, we're just gonna run
2075.04 -> this file as a script, just so we can review this
spreads index. So if I give that a go, we kind
2083.04 -> of make this bigger. Notice that I have correctly
spread things out right? Have Alvin at the front,
2088.32 -> and I have all of the things from peeps in the
middle, right, followed by Brian at the end.
2093.6 -> So you can do this. You can also use like the
concat method on arrays. You're probably going
2098 -> to see me use this spread syntax a lot because
I'm kind of a fan, right. But with that in mind,
2104.8 -> let's go ahead and actually test this code. So
we'll run all the test cases. Nice. And this
2112.56 -> is another working solution for our depth first
values. And it should be pretty natural that we
2119.28 -> can solve this problem also recursively. So I know
that the iterative solution for this depth first
2124.4 -> traversal requires a stack data structure.
And I know whenever I write recursive code,
2130.24 -> under the hood, your programming language is
actually going to track all those recursive calls,
2134.48 -> using the call stack, right? That call stack
behavior gives you the same type of ordering,
2139.2 -> which is really convenient. Cool. All right.
So before I send you off on the next problem,
2143.76 -> I want you to actually practice both solutions
for this depth first values code, it's going to be
2149.12 -> very necessary to actually master some later
concepts that are coming right up. So do spend
2154.08 -> some time on this practice makes perfect,
right, and I'll catch you in the next one.
2162.72 -> Hey, programmers, Alan here, right? Now I want to
go over this breadth first values problem. So it's
2167.68 -> really just going to be a little variation off of
the depth first one we just did, of course, but
2171.68 -> it's really important that moving forward for all
of our tree algorithms and other data structures,
2175.76 -> that we have both versions down pat. So in this
problem, we're going to take in a binary tree,
2180.96 -> once again, very classic binary tree structure,
this time, I want to return an array or a list
2186.24 -> of all the values according to a breadth first
traversal order. So a breadth first traversal
2191.76 -> starts with the root node of a, so that's
nothing new. And then from there, I could
2195.52 -> go to B. So right now I have my a node, and also
my B node. And here is where we diverged from our
2201.92 -> previous problem in a breadth first traversal. And
breadth just refers to like the width of something
2207.36 -> I travel across before I go deeper. So in our
breadth first traversal, I'm gonna move to C
2213.52 -> and not D for now. So I add my C node c value to
my list. And then from here, once I finished this
2221.28 -> entire level, and there's nowhere to go across
the tree anymore, now I could go downward to the
2226 -> next level. Now I have D, and then E, and then F.
So they're really important distinction here is
2233.6 -> the breadth first traversal starts with
ABC, whereas the depth first traversal
2237.84 -> would have started A, B, D. That's a
really, really important distinction.
2243.68 -> And so how can we go about implementing
the breadth first version of this?
2247.76 -> Well recall that the depth first used a stack
data structure, well is the case that the
2253.44 -> breadth first is now going to use the queue data
structure, really just the partnering version
2258.24 -> of that structure. And so let's kind of step
through that in a more programmatic way. So I'm
2262.72 -> going to use and track my queue. And just recall
that a queue has no sense of direction to have
2268.32 -> the back of my queue and the front of my queue,
things enter the back of the queue, and they leave
2274.16 -> the front of the queue. Right. And so no one gets
a skip line either. So this gives me a nice fair
2279.68 -> ordering, think of a queue as just like waiting in
line at checkout at a grocery store or something.
2284.72 -> So how do I begin my algorithm, I'm going
to start by initializing my queue with the
2289.84 -> root node. So I'm just gonna start with a on my
queue. And then from here, now I can begin my main
2295.52 -> algorithm. So my main algorithm should check
on every iteration is my queue empty, right now
2300.96 -> it's not because I have at least one element.
And so I remove the front element of my queue.
2307.84 -> And so we know that a would be removed,
and we label it as our current.
2311.6 -> A node being explored when something leaves
the queue and is marked as our current will
2315.92 -> say that now it's being visited. So I would add a
to the running list of my values. Then from here,
2321.92 -> I need to look at his children. He has two
children B and C, I need to go ahead and
2327.28 -> add them into my queue. And so let's say I
added B into the queue first, followed by C.
2334.64 -> Notice that C must enter behind B, right. And
now I finished this iteration. At this point,
2340.16 -> I have the next iteration of my algorithm, I take
the front element of my queue, and it leaves,
2345.12 -> right So b is now my current, I add B to my
running list, then I look at B's children of D,
2350.8 -> I push D followed by he behind it. At this
point, I have another iteration to do right.
2356.56 -> And it's so on so forth. From here, see leaves the
front of my queue, I add it to my list of values,
2362 -> and I look at sees children see only has
one child. So for that child that exists,
2367.36 -> I go ahead and add them to the back of my queue.
And it's really important that I added to the back
2373.2 -> right at this point had my next iteration. At this
point I continue, my queue is still not empty, so
2377.12 -> I still have some stuff to remove. So D leaves in
front of my queue, I add it to my list of values.
2382.4 -> Since D has no children, there's nothing to add
here. next iteration, he leaves the front of my
2387.28 -> queue, I added to my list of values, no children,
so I don't need to add anything. And finally f
2392 -> leaves the front of my queue, I just add it to my
list of values and again, f has no children. So by
2397.44 -> now my queue is empty, which must mean that, hey,
I must have completed the algorithm, right? There
2402.96 -> are no more nodes to explored, I explored and
added every single node to my list of values.
2409.28 -> All right, and this output actually looks correct,
right, I get abcdef, just like we say. But what
2414.8 -> about the complexity of this algorithm. So
let's take a closer look over here. Well,
2420 -> we know from the get go, that n is going to be the
number of nodes in this binary tree. So that will
2425.28 -> be the term for our sides of input. And we can say
that the time complexity is simply just O of n,
2431.68 -> roughly, because we know when it comes to visiting
these nodes, and you know, using our loop,
2438.08 -> we're going to add every node to the queue once,
which also means that that node is going to leave
2442.96 -> the queue also wants, so it's not like we're
double adding a node to the queue, right,
2447.28 -> we're not going to double visit any of these. In a
similar way, the space complexity is going to be O
2451.76 -> of n at most, because, you know, we're just going
to add at most to all of the nodes into our queue.
2457.2 -> And in general, it's probably going to be less
than Oh, event space in terms of how much space
2460.96 -> we use in our queue. An important thing I'll
just mention right now that in regards to the
2465.2 -> time complexity of this one, here, we're going
to say that the time complexity is O of n. And
2470.56 -> that's if we can assume that adding something now
to the queue runs in constant time. And removing
2477.28 -> something from the queue occurs in constant
time. So depending on how you implement this,
2482 -> if you use actually, a built in an efficient queue
data structure, you will get this O of n time
2487.36 -> complexity for our breadth first. But if you use
a less optimal, like data structure, maybe not a
2493.44 -> perfect queue, then you might have an actual worse
complexity. So again, this time complexity of
2499.2 -> O of n assumes that we have a maximally efficient
queue that has o of one add and remove operations.
2507.36 -> With that being said, I feel pretty good
about coding this one up. I'll catch you
2511.44 -> in the walkthrough video, and I'll show you a
few different ways that's implement this one.
2517.6 -> Hey, programmers, Alvin here, right now I want
to walk through the JavaScript solution for this
2522 -> breadth first values function. So hopefully,
you just finished the depth first version,
2526.8 -> in which case, this one should be pretty much a
cakewalk. But of course, we will still go through
2532.32 -> the motions of it, because it's going to be useful
to solve much harder problems later on, as you
2537.36 -> always hear me say, Alright, so to tackle this
one, we'll start with our queue data structure,
2542.32 -> right? So nothing fancy in JavaScript, what I
would do is just use an array and just stick to
2546.56 -> using very specific methods, right? So I'm
going to create an array, I'll call it my
2552.08 -> cube. And we're going to initialize that queue
with the route on it by default. And we'll also
2557.52 -> guard against upfront is imagine they gave us
an empty tree to begin with. So in other words,
2562.88 -> the initial route is no, which case it would
be like this test 04. And they just want us to
2567.84 -> return an empty array. So I'm going to guard for
that explicitly. So I'll check Hey, is my route
2573.04 -> No. And if it is, just go ahead and return an
empty array like that. Nice. Then from here,
2581.2 -> I need to start in my main loop from algorithm.
So I iterate a while my queue is not empty,
2586.96 -> just like we spoke about in the approach video,
right? So while q dot length is greater than zero,
2592.96 -> then keep on going. Now I begin a single iteration
of this algorithm by just removing the front
2599.84 -> of my queue, right? So it's really up to you which
methods you use, you just need to make sure you
2604.8 -> remove from one end and add to the opposite end.
So for me, I'm going to treat index zero as if
2610.72 -> it's the front of my array, I'm going to treat
the last index as if it's the back of my array,
2615.92 -> right? So if I want to remove the front and say,
array dot shift, or for me right now, Q dot shift,
2621.52 -> that removes the front also returns to me, that
element, so I'll call that my current note,
2627.84 -> x. And then from here, I need to add this node
children into my queue. And that'll give me my
2634.88 -> main flow for this breadth first traversal.
Right. So I'm going to go ahead and check,
2641.04 -> hey, if my left child exists, so if, let's
say current dot left, that is not know, then
2649.76 -> what I should do is go ahead and push that into my
queue. So I'll say q dot push my current dot left,
2659.84 -> and it's just going to be symmetric
for the right hand side, of course.
2664.32 -> So if the right exists, then push the
right into the queue. Just like that.
2672.4 -> Awesome. And so that looks pretty good. And
then from there, I actually want to store
2679.6 -> the nodes I visit in an array for the
final return just like the problem asks,
2684.64 -> so nothing too fancy. I really want to insert some
code over here about and so I'll create a result
2690.72 -> array, I'll call it values, sort of empty whenever
something leaves the queue. I'll just take that
2696.4 -> and push it into my values. So I say values dot
push. I'll push that current Val into my queue.
2704.32 -> And do note that, what you can't do is just take
like the queue and treat it like your final return
2710.56 -> value, it must be a totally separate thing,
right, I use the queue just for the sake of
2714.72 -> traveling through in a breadth first order. And
the order that you visit is actually derived from
2720.64 -> the order in which things lead the queue.
So that's why I'm doing it over here, right,
2725.04 -> as soon as something leaves a queue, that's what I
considered visited. So I added to my values list.
2730.16 -> Nice. And after my while it's done running,
I'll go ahead and return my entire values array.
2737.6 -> So let's give this a test. I'm gonna
run all the test cases, what we get,
2742.16 -> have a few test cases to pass. And there we
have it. Here's a nice iterative solution for
2747.92 -> our breadth first traversal. Just something I want
to mention, by the way, let's look at the prompt.
2754.48 -> So looking at, I don't know, like the very
first example, in this kind of rendition of
2760.4 -> breadth first, what they asked us to do is
really give us a breadth first traversal,
2764.48 -> that moves from left to right, so notice it goes
A, B, C in terms of the resulting output, and
2770.96 -> not a CB, right, those would both be technically
correct, start to a breath first. And then you can
2777.52 -> kind of choose depending on what problem you're
solving, whether you want to go left to right
2780.96 -> or right to left. For me, because I push the left
followed by the right, that means the left is
2788.88 -> going to leave the queue first, right, because
remember, the queue is just like a line and
2792.4 -> checkout. So if someone enters first, that is the
left enters first, they going to be served before
2798.32 -> the right go. And you can just flip these around.
And I'll give you the right to left universal
2804.08 -> goal. So depending on what your problem warrants,
you can always manipulate that code a little bit.
2808.56 -> And this is actually probably like the only
solution you can have. You know, maybe aside
2814.16 -> from just some superficial changes to like the
code style, this is going to be your go to and
2818.56 -> only go to solution for a breadth first traversal
on a binary tree, right? A common mistake I see
2823.68 -> people try to do a lot is there is not really a
straightforward way to implement a breadth first
2829.12 -> traversal recursively. And that should make
some sense, because a breadth first traversal
2834 -> needs a queue order right needs to use a queue. If
you write any recursive code, you know, under the
2839.2 -> hood, it's using a stack. And so that stack versus
queue is really just going to fight against you.
2844 -> And you're going to have a really tough time
trying to implement the correct ordering.
2847.12 -> So always just writes the iterative version
for your breadth first traversal. Alright, so I
2854.08 -> recommend before you hop into the next video, make
sure you're able to write this code on your own,
2858.24 -> because we are going to level up difficulty a
little bit, but I'll catch you in the next one.
2866.64 -> Hey programmers, Alvin here, right now I
want to walk through the approach for this
2870.56 -> tree includes problem. So the premise of this
problem is I'm going to give you a binary tree,
2875.84 -> and also a target value to look for. I
just want you to tell me True or false?
2880.88 -> Is that target value found within the binary
tree? So for this particular example input,
2886.16 -> the answer is obviously true or Yes, right, you
could definitely find e within this binary tree
2891.12 -> for give you another target value like
j, you would respond with false, right?
2895.36 -> Because that value j is nowhere to be found within
the binary tree. And really what I'm asking you to
2901.44 -> do here is we're stepping through the canonical
like breadth first search and depth first search
2907.36 -> problems. And I think I'll walk through both
approaches for you right now. So let's say I
2913.28 -> was testing or I wanted to trace through rather of
the input where target was IE, how can I go about
2919.2 -> attacking this one, right? We know that in
most of these problems, when they give you
2924.08 -> a binary tree as input, they're only going to give
you really the root node. But that being said,
2929.76 -> if you have access to the root node, then you know
you have access to all nodes that comprise of the
2934.8 -> tree, right. So what I can do is just perform any
of my traversal algorithms. So maybe to get going.
2941.28 -> Now let's just do either the breadth first search
or the depth first search iterative style. So I
2948.32 -> think for this trace, I'll stick to the breadth
first version, which means we're going to use a
2953.92 -> queue, right? So as we trace through this, I'm
thinking about this one iteratively. Right now,
2959.04 -> hopefully you recall from our previous problems
when it comes to your breadth first traversal,
2963.36 -> you start with your root node on your
queue. And when something leaves the queue,
2968.08 -> you mark it as your current right. And here's
where I work in the new logic for this,
2972.88 -> this particular problem. When something leaves
the front of my queue, I'm going to check Hey,
2978.08 -> is that current value the same as my target value,
so is a the same as E. It's not. So I have not
2984.88 -> found the thing I'm looking for, right? And what
I can do is now consider his children. Right? So I
2990.8 -> look at his children. They both exist, I add them
to the queue. So I'd be to my queue that I add see
2995.84 -> to my queue. And now I'm on to my next iteration
right? The front end element B leaves a queue,
3001.84 -> and I have to check, hey, is B, my target,
it's not right my target t. So I keep running,
3006.96 -> I look at B's children. So I take that D and
added it, I take the E and also add it. And this
3013.76 -> process just continues, see leaves front of my
queue is see my target, it's not. So keep going,
3021.44 -> I would add C's children to my queue. So I just
add F to my queue. And this process continues.
3027.6 -> And so d leaves the front of my queue I check is d
my target, it's not, and D has no children to add,
3034.16 -> right? Recall that in our breadth first traversal,
I only add the children if they exist, because I
3038.88 -> don't want to add any, like null pointers into
my queue. And so I just continue my algorithm,
3043.84 -> right, I still have stuff in my queue to check.
And finally, when he leaves the front of my queue,
3048 -> I check Is he my target. And indeed it is right at
this point, I've just confirmed that he is found
3055.52 -> inside of my binary tree. So what I can do is just
end my algorithm by like returning the true value,
3061.44 -> right? There's no point of actually looking
through the rest of the tree, because I already
3064.96 -> figured out that, hey, my target value is indeed
within the tree. Right? One thing you might notice
3071.44 -> is, it looks like I only checked for IE once
it left the front of my queue, and not when it
3078.32 -> was initially added to my queue. Technically, you
could have returned early when you added it to the
3082.96 -> queue. But we'll kind of see when I walked through
the full code for this one, it would end up with
3087.52 -> cleaner code if you just checked for your target
value when something leaves your queue. So we'll
3094.72 -> see that when we go through the code. It's just a
small implementation detail. That being said, for
3099.04 -> this iterative breadth first strategy, what can
we say about the complexity? Well, if we define n
3104.88 -> as the number of nodes, then we know that the
time complexity is just O of n, it's really just
3108.96 -> a classic breadth first traversal. So nodes
are going to enter the queue once and leave
3112.88 -> the queue once that's open, right. And again,
that's considering if we use a efficient queue,
3118.16 -> right, where our queue add and remove operations
run an O of one constant time. So we have linear
3123.76 -> time. And for the space complexity, it's also
going to be O of n linear, right? Because we're
3127.6 -> just going to store our nodes within the queue.
And so we just looked at the approach for a nice
3133.92 -> iterative breadth first solution, not to this
problem, but I want to show you the depth first
3139.52 -> version, and the depth first version, that would
be recursive, right? So obviously, you could write
3144.96 -> the iterative debt per solution, which case you
just use basically the same code we just spoke
3149.68 -> about, but just use a stack instead of the queue.
But let's try to solve this one. recursively,
3154.96 -> right. And the reason I think it's really
important to expose yourself to recursion like
3158.96 -> this is, as we move to more complex topics, you're
going to find this style of recursion. Very, very
3166.32 -> useful, right? So we have the same input, right?
Let's say My target is E, and I have the same
3171.36 -> binary tree. And now I want to check recursively
is E within this tree? And so how do we start
3178.08 -> attacking this? Well, we're going to need to think
about our base cases, right? So we're gonna have
3183.44 -> really two types of base cases, we'll have
like the affirmative base case, meaning Hey,
3187.52 -> we found a match. And so whenever I counter a
node, whose value is he, or whose value matches
3193.6 -> my target, then I'm gonna have that node or that
recursive call, return true, right? So that's my,
3198.88 -> like, affirmative base case. So I'm just gonna
plug that return value in visually in my tree,
3203.6 -> you know that this II nodes gonna return true. And
now I'll think about my negatory base case, right?
3210.32 -> Four times where I call upon an empty
node, or the null node, I should return
3217.04 -> false. And recall from our previous lectures,
we said that we're going to sometimes represent
3222.32 -> explicitly our null nodes. So I'm going to fill
those in, for example, the C node in my picture
3228.4 -> would have a left child that is null. So I'll kind
of draw that one explicitly. And I know that a
3233.04 -> node like that is going to return false. Because
logically, I shouldn't be able to think about
3238.24 -> all of my recursive calls as if they're their own
subproblems. Right? So if someone asked me, Hey,
3244.4 -> can you find this E value within an empty tree?
Right? a null node represents an empty tree?
3250.16 -> The answer to be no, I can't find the value in
an empty tree, because there's nothing there.
3254.64 -> And so from there, I'm also going to draw
explicitly all of those similar null nodes,
3260 -> null pointers, right? So it looks something like
this. Notice that from the E node, I don't need to
3265.92 -> give it a null left and right, because I already
said that that node is going to return true,
3270.56 -> right? So that's why I draw my tree like this.
And I have all of those false return values.
3275.84 -> Cool. So we just labeled all of the base cases,
right as the leaves of our tree, and recall that
3282.16 -> a leaf is just a node with with no children,
right? And from here, how do I actually combine
3289.12 -> all of these Boolean values to get the true at
the very top, I know for my top level color,
3295.28 -> that is at the a node, or the a recursive call,
I need to get back that value of true, right?
3302.48 -> And the logic we should use is really just
to the logical OR so how does this one work.
3309.12 -> So let's start evaluating our return values and
combining them at the parent. So this should be
3315.68 -> somewhat of a similar pattern to like the tree
sum problem I showed you. And so what you could do
3321.12 -> is focus on this D node over here, this node has
values ready on its left and right has two falses.
3329.04 -> And when it actually gets those falses returned to
it, it just should do the logical OR so it's doing
3334.8 -> false or false, which evaluates to false, right?
Which means that hey, in this subtree rooted in D,
3341.36 -> I cannot find the value, which makes sense. That's
why it's false. I'll continue this process. If I
3347.44 -> look at this B node, now this B node has values
ready on its left and right. And they're going
3352 -> to bubble up a little bit. And I take the order
of them so I do false or true, which evaluates to
3358.24 -> true. And this process continues everywhere in the
tree, right? So at this f node, false or false, is
3364.32 -> me false. At the C node, false or false gives me
false. Finally, at the top level root of A, I do
3373.12 -> true or false, give me back a final true, which
is indeed the correct answer. So hopefully,
3379.2 -> you realize how similar the solution is to our
previous tree some problem right in the tree,
3384.08 -> some problem, I combined my left and right,
child return values by doing the arithmetic
3390.32 -> addition. But this time around, I just need
to use the Boolean operation of or right,
3395.52 -> so by just adjusting the type to Boolean, we
have a very, very elegant solution that shout
3400.72 -> out George Boole. And so with that, I think let's
go ahead and implement this one in some code,
3406.16 -> and I'll show you it using the interest of
flavor or using maybe a breath for us, and also
3411.36 -> the recursive version, which is my personal
favorite, using this recursive tree structure.
3419.44 -> Hey, programmers, welcome back. Alright, and I
want to go over a JavaScript solution for this
3423.44 -> tree includes problem, right? Well solve this both
depth first, and also breadth first. And I think
3429.04 -> we'll start with the iterative breadth first
version. And so this is really just going to
3432.8 -> be implementation of the classic breadth first
search algorithm, I'm just gonna lay down my
3437.92 -> classic a breadth first traversal code, and then
just add some conditional logic afterwards, right?
3443.6 -> So you should be familiar with it by now. But for
my breadth first traversal, I'm going to use a
3450.88 -> cube. So I'll say const, q equals an empty array,
are really an array with the route thrown on the
3457.28 -> inside. And from there, I have my main algorithm,
right, so I loop while my queue is not empty.
3463.04 -> So while queue length is bigger than zero, and
keep on going. And on a single iteration of this
3469.04 -> traversal, what I do is Q dot shift, so remove
from the front of my queue, the front of my array,
3475.28 -> remove the first element. And I'll save that into
a variable called current. So that will be just
3481.36 -> an instance of node. And for now all why don't
I just build up my solution slowly, I'll just,
3485.92 -> I don't know, console dot log, what current
dot Val is. But once I consider this node,
3492.88 -> what I want to do is really add its children into
my queue only if they exist, though, right? So in
3498 -> general, I'm going to write like q dot push,
I'm going to add to the back of my queue,
3502.4 -> so I get a nice cue order, push the left child,
so current left, likewise, the right child.
3509.68 -> But imagine that I have an asymmetric node or
just a leaf node, right? Something like C would
3515.28 -> only have a right child, so it's left would be no.
So if current is see, then I'd be pushing No, into
3523.68 -> my queue as the left, which is no good, right. And
so I need to guard here and only push the children
3529.6 -> if they exist. So something like this, hey, if the
current has that, corresponding left and right,
3536.64 -> then I can go ahead and push it. So this is
looking pretty good. And that should actually be
3544.48 -> the main traversal part of the code. So I'll
just test this manually. So very manually, so
3551.68 -> maybe just this call, so I'm not gonna return
Booleans yet. We'll build up to that. But I
3556.08 -> should at least see my values printed. If I kind
of run this manual test case, I'll bring in my
3561.2 -> node class, I should see the values printed in a
correct breadth first orders, that means A, B, C,
3568 -> D, E, F, recall that breadth first traversal
travels across our tree before going lower,
3573.52 -> so I must finish a level before traveling to the
next level. So let's just run this manually as
3578.96 -> a script. See what we get here. A, B, C, D, E, F,
nice, so I'm getting the right order of traversal.
3587.2 -> And now I can work in I think, the conditional
logic because they want us to return Booleans
3594.08 -> over here. So pretty straightforward stuff. We'll
go ahead and check once something leaves the
3599.28 -> queue. I can check If the current nodes value is
equal to my target, then I've found the thing I'm
3605.68 -> looking for. So just return true, right, you're
done, you don't need to travel through the rest
3610 -> of the tree because you can return true. But on
the flip side, if my value that I'm currently at
3617.6 -> is not the target value, that I must continue
looking through the rest of the tree, right.
3623.12 -> So if I finished the entire while loop, that means
I've traveled through the entire tree. And I never
3627.84 -> found the thing I'm looking for, I should return
false. So I need a late return false over here
3634.08 -> are really common mistake people tend to make is,
3637.36 -> what you don't want to do is just do like, else
return false here. So this is going to be wrong.
3646.16 -> Right? Because this would only check like the very
first notice normally check the root, and then
3651.52 -> check if the root is not equal to the value.
If it's not, you just return false, which is
3657.04 -> not really useful, because it could be somewhere
else in the tree. So you're gonna need that late
3660.72 -> return false pattern over here. But with that, I
think we're going to pass some of the test cases,
3666.88 -> as well run the test cases by hitting that test
button. And there's probably one scenario we
3671.76 -> did not for C. Cool, and there it is, right? Can I
read property value? No, we're failing tests. 055,
3679.92 -> look at that spec. Test five gives us a null
node as a root, right? So just the empty tree,
3687.12 -> you cannot find the B character inside of the
empty tree. So return looks like false over here.
3692.48 -> And so I can just handle that one explicitly.
I'll go ahead and check at the top. If my
3698.8 -> route is no, right, if that's the case, then just
return false. I can't possibly find any target
3706.08 -> in an empty tree. Right? The reason our
code was failing before is if root is null,
3711.68 -> then I initialize my queue with no. And when
that thing is pop, and that null is popped,
3716.88 -> or rather shifted from the queue in the first
iteration, then I check null dot Val, which
3722.08 -> is an illegal JavaScript operation.
So I'll run all these test cases now.
3729.84 -> Nice. And there, we have our breadth first
solution for this tree includes problem.
3735.76 -> All right, now let's work on the recursive depth
first version of this, it's actually my personal
3742.16 -> favorite, because it utilizes a pattern that I
think is quite elegant, and one I use a lot for
3747.52 -> much more difficult problems. So like we said,
in the approach video, if you haven't watched
3752.08 -> the approach, you definitely want to check
it out. For this recursive version, right?
3756.24 -> what I should do is check Hey, if my root is
null, if I have the empty tree, basically,
3761.12 -> then just return false, right, because I can't
possibly find my target and empty tree, right,
3765.44 -> that's just a given. And from there, I know I'm
going to have the general shape of some just
3770.08 -> depth first traversal code, which means you call
the same function because it's recursive. That's
3774.4 -> what recursive means. And you pass along your
route dot left and a separate call your route,
3779.12 -> right. And when I should be sure to do
is Don't forget to pass in your target,
3782.88 -> write the target that you're looking for, it never
changes. And I know that these two these two calls
3790.24 -> are going to give me back boolean data. And I
know that the Boolean I get back from like this
3794.32 -> call would represent whether or not I found the
target and that subtree, right. So this gives me
3798.72 -> the result of if I found it in the left subtree.
Or the result if I found it in the right subtree.
3803.36 -> And I can just do the logical OR on both of
these, right. So if I find it in either subtree
3810.96 -> then return true. So I could just write in line
return true over here, right? So let's say it's
3816.16 -> in my right subtree, then this left hand side
invites to false. And this is true, in which case,
3822.64 -> this entire thing evaluates to true. And let's
say in a bad scenario, let's say it's not found in
3828.4 -> either subtree. So this evaluates to false. this
right hand side also evaluates to false, false
3833.2 -> or false gives me false. However, one thing I need
to be sure to add is also an additional base case,
3840.16 -> after I check if my route is no, what I want to
do is then also check, hey, maybe this route I'm
3847.68 -> currently at, maybe it actually has the target,
right? So if route value is equal to the target,
3853.04 -> then you're also done, except you can return
true. Cool, and that was very reminiscent
3859.04 -> of our approach video. So let's give this a shot.
You should be able to pass nice, and I love how
3867.44 -> clean this code is. I will admit, you know, it's
pretty tricky. If you're not a fan of writing
3872 -> recursion, in which case, I'll totally convinced
you into being a fan of recursion. But notice how
3878.16 -> kind of clean this code is really leverages
recursion. One very important thing I want to
3884.08 -> bring up is it's really keen that I put this
base case on line 26 after the null check,
3891.6 -> right? So let's say I flipped the
order of these. Let's say you did this.
3894.48 -> I believe that would not work out always because
it assumes that you even have a route Alright,
3900.56 -> so I'm feeling a test 00. But in general, if you
look at this code, let's say that route was no,
3907.44 -> right? You're gonna start by checking
null dot Val, and I'll throw an error,
3911.6 -> right? Can I read property valve? No. So you want
to actually always lead with your base case that
3917.36 -> checks if your root is null, right? Because that
should guard really the entirety of our code. So
3923.2 -> this is actually the code you want. Over here.
Alright, programmers. So that's all I got for this
3927.84 -> tree includes solution, I want you to practice
both versions, and I'll catch you in the next one.
3937.36 -> Hey, programmers, Alvin here, right? Now I want
to go over the approach for this tree sum problem.
3943.2 -> And so in this problem, I want to take in a binary
tree, just like we've been doing as of late,
3948 -> this time, the values within the nodes of this
binary tree are going to be numbers, right,
3953.04 -> what I want you to do is compute the total sum of
all the values in this tree. So for this example,
3957.92 -> we should end up with 25. And so hopefully, you're
kind of gathering how to attack this problem,
3965.04 -> especially given you know, the algorithms I've
been showing you as of late. So if you've been
3969.28 -> studying our problems, and are there hopefully,
you know, a straightforward solution to solve
3973.44 -> this one, we could of course, just use any type
of traversal algorithm. So we can use either a
3977.52 -> breadth first or a depth first traversal. And we
can just add all these values into a running sum.
3983.12 -> And of course, we probably initialize that sum
to zero, right? So the iterative breadth first
3988.56 -> or depth first solution, I think, is very
straightforward, right. And I'm not going
3992.88 -> to really step through that approach with you
over here, I think you have that one down pat,
3996.64 -> especially if you've done the previous two
problems. But what I will show you here is
4000.96 -> actually how to solve this one recursively, which
would be a type of depth first traversal, because
4007.36 -> we know that hey, depth first traversal relies
on a stack. And if you do something recursive,
4012.48 -> it is utilizing the underlying call stack.
So I will get a similar type of ordering.
4018.32 -> And so when we trace through this type of
solution, this recursive solution for this tree,
4024.16 -> some problem we're going to do is try to be
very explicit, I think this is really helpful,
4028.88 -> especially if you struggle with recursion,
right? So given this binary tree, I know that
4035.2 -> for particular nodes of my tree, like the four
node, it does not have a left child, right. And
4042.48 -> I know like programmatically, what that means is
like that nodes dot left pointer points to like,
4047.84 -> no, or it's a null pointer. And so I'm just
going to draw that explicitly, sort of like this.
4053.84 -> Again, they'll just help us really understand how
our recursive code performs on this type of input.
4060.88 -> And so if I know that I can put like
an unknown load to the left of four,
4065.04 -> then it could be the case that other nodes like
the leaves have to in one, they also have both
4071.28 -> left and right children that are also know. So
if I drew all of my null pointers explicitly,
4076.56 -> it would look something like this. Cool. And this
is really something that helped me really get
4083.92 -> comfortable with recursive problems, especially
those on binary trees. And what we're doing now
4090.88 -> is, we know that when it comes to solving any
problem recursively, it's about writing a base
4096.08 -> case, that is like the simplest version of our
input. And here, I'm going to argue that our
4100.96 -> base case needs to be about the null node, right?
The null node basically represents no node at all,
4107.52 -> or represents the empty tree in a sense. In other
words, if someone asked me to calculate the sum
4114.16 -> of a null node or the sum of an empty
tree, then to me that some would just be
4118.96 -> zero, to write elegant recursive code
to try to think about your base case
4123.04 -> as a problem in itself, right? So if someone
gave me an empty tree, that is a null node,
4128.48 -> I would return the total sum of zero. And what
that means is I know that all of these null nodes,
4133.68 -> they would return zero as their computed sums.
Nice. And then from there, how can I use this
4140.56 -> information to actually build up my main solution?
Right? So let's go ahead and target this for node
4147.12 -> to the left. And what I have to do is figure
out Hey, know what is this subtrees total sun,
4154.4 -> and I can compute that given the values
to the left and right. In other words,
4158.88 -> if I return those two null values returns to zero.
Now I just have to do zero plus four plus zero,
4166.72 -> which just equates to four, right? And that is
actually correct in itself, right? So what green
4172.24 -> number above a node represents the total sum
of that subtree. And so it is a case that, hey,
4178.16 -> the total sum of that four node is just four.
And I would do something similar for this node
4183.84 -> over here, right? When these base cases return
to their color or return to their parent, I just
4189.92 -> have to add my left and right child together
along with myself. So zero plus two plus zero,
4195.44 -> gives me to not do that same thing. For this note
11 We're here. And now things get interesting,
4201.36 -> right? It's a calculate the total sum rooted at
this 11 subtree, I would just return these values
4208.48 -> to the top. And now I do four plus 11 plus two,
which gives me an answer of 17. And if you do a
4214.8 -> quick spot check, right, this 17 does represent
the total sum, just in this subtree, right,
4223.68 -> and we'll carry on over at this one node, we know
that this is going to return just a value of one.
4230.48 -> And now at this four node, I can compute its total
sum. And recall that this four node had a left
4235.84 -> child of zero, right? Because it has a null node.
And so when I compute the sum, I get five, which
4242.88 -> is perfect. And finally, at the main route, now I
bring up these two values. And I compute 17 plus
4250.08 -> three plus five. And that gives me a final answer
of 25. Which is indeed the correct answer. Right?
4256.8 -> So that's how we should really think about our
recursive algorithms for our binary trees, right?
4262.16 -> I kind of draw it out, I think about the
base case, which is typically not always
4266.64 -> but typically about the null node. And then from
there, I figured out how a parents can compute
4272.72 -> its result given its children's answers. Alright,
so if we take a look at the complexity of this,
4279.44 -> it's pretty straightforward. We'll go ahead and
define n as the number of nodes in our input tree,
4285.04 -> in which case, I can see that my time complexity
is just O of n, right? We know that we're going to
4290.48 -> make a recursive call just for every node of the
tree. And we're not going to call duplicate nodes,
4297.52 -> right, we're going to have just one call for every
single node. And within any single node, we're
4302.56 -> just going to do some simple arithmetic, right, we
just had roughly three numbers together. So it's
4306.64 -> not like we're going to have like a loop inside
of our calls at all. In a similar way, we'll say
4310.96 -> the space complexity is O of n, just because we
have that implicit, a call stack space, because
4316.48 -> we are going to solve this one recursively. And so
we're solving this one in O of n time and space,
4321.76 -> which would be actually a maximum efficient a
solution for this problem. And so with that,
4327.6 -> I think, let's head over to the walkthrough
video, and I'll show you how to code this one up.
4335.12 -> Hey, programmers, Alvin here, right? Now I want
to walk through the JavaScript solution for this
4339.68 -> tree some problem, I think this time around, and
I'll jump right into the recursive version, right?
4346.4 -> So we'll start recursively. And we'll begin with
our base case, right? My base case is always about
4351.44 -> the simplest version of the input, where
I just know the answer without needing
4355.12 -> any additional calculations, right? I know
that the simplest tree here that I could be
4359.28 -> given is going to be the empty tree, right? I
have the empty tree. That means my root is no.
4365.44 -> And if your root is no, you have the empty
tree. What is the sum of the empty tree? Well,
4370.4 -> kind of inherently, it's just zero. So I'll
be my base case. Nice. And then from there,
4375.68 -> I'll think about how I can compute my answer,
given my children results. So I need to find
4382.56 -> the results of the some of my left subtree.
And also the some of my right subtree. So
4386.88 -> just call recursively. So tree, some of root
left, as well as tree some of root. Right?
4395.28 -> Cool. And I know that these two calls, they return
numbers, right, representing the sum of my left
4401.92 -> subtree. And the sum of my right subtree. As the
parent that is so rude, how can I find my total
4408.16 -> sum? Well, it just is myself. So root out value,
plus everything in my left subtree plus everything
4415.76 -> in my right subtree. Right. And we'll go
ahead and just test this out the gate.
4421.84 -> But this is nothing fancy, really elegant code
to look at the test cases here, we do have some
4428.64 -> a diverse output. So this code does work on trees
of all different shapes and sizes. Something that
4435.68 -> helps me you know, really believe the magic of
recursion is to just analyze the assumptions here,
4441.6 -> right? So let's say that I'm stepping through tree
some and my root is this three over here, right?
4447.28 -> So I checked the base case, is this three node?
No, it's not. So I must make the recursive call,
4452.56 -> right. And I know that when I break down this code
recursively, I know my route that Val is going to
4457.68 -> be like three, so I'm kind of corresponding, this
comment with the thing below, right? And then
4463.28 -> when I make the recursive call on tree, some root
dot left, that means I'm asking for the total sum
4468.72 -> of this subtree starting at 11. So I'm looking
at the 11 for negative two subtree. Right,
4475.12 -> if I take the total sum of just that left
subtree, it looks like it's going to be just
4481.76 -> 13. It's now I'm saying plus 13 over here,
right? If I do the same thing on the right,
4486.72 -> subtree I know that this call is for this
four node, right all of its children,
4492.48 -> that should just magically return by the
power of recursion that should return
4495.84 -> five, right? I'm going to assume
that that recursive call just works.
4500.8 -> So you're out the five, right? If I take the total
sum of these, three plus 13 1616 plus five is 21.
4507.44 -> That would give me the correct answer, right.
So to have some confidence in my recursive code,
4512.4 -> I just write the code. And then I assume
correctness from my recursive calls. And
4517.76 -> I figure out how I can take those sub valleys
for my children, combine it with my own value,
4522.48 -> and that should be my final answer. So here
is the recursive version of this solution,
4529.44 -> which would be some sort of a depth first
traversal, technically, because it's recursive.
4533.68 -> And if you'd like, I can also show you the
iterative version. So let's just do that.
4539.52 -> And I always practice usually my problems doing
both the recursive as well as iterative version,
4544.8 -> if it's reasonable, and is really reasonable
here. Hopefully, you're familiar with
4548.4 -> our breadth first code by now, right? So I'm just
gonna start by checking, hey, if you're given some
4553.84 -> root that is already know that that's kind of an
edge case, I'll just go ahead and return zero,
4559.2 -> right? Because as some of that empty subtree,
or that empty tree, rather, is just zero,
4563.44 -> that can begin my main code. So while my
queue is not empty, so I'll start with a Q,
4570.96 -> who begins with the Route Route, I want to loop
while my queue is not empty. So while q dot
4578.72 -> length is bigger than zero, I'll begin a single
iteration of my while loop by just shifting out
4584.96 -> the front of my queue. So in JavaScript, for me,
that's q dot shift that removes the front element,
4589.36 -> and also returns it to me. So I'll save in
current. And then from there, now that I have
4593.44 -> this current, I know that contains the value
that I actually care about. So what I would do
4598.56 -> is go ahead and track some running sum. So I'll
say let some member say let total sum equals zero.
4606.72 -> And as I remove something from the front
of the queue, I'll take it to value
4611.04 -> and add it to my total, something that will
accumulate all of the values right into a
4616.32 -> sum. And from there, I just need to add my
classic logic of checking for my children,
4620.96 -> right? If they exist. So if I have a left,
so if current dot left is not equal to know,
4626.96 -> then what I'll do is add that left child into
my queue. So q dot, push my current dot left,
4635.28 -> again, make sure you're following your cue
rules, right, so shifts removed from the front,
4639.68 -> push adds to the back, it's really important that
my shift and my push or my add and remove methods
4645.12 -> work on opposite sides of my queue. Otherwise,
it's not a cue, right? So that looks good to go.
4649.76 -> I'll write something symmetric. For the right
hand side over here. By the end of my function,
4656.16 -> I'll just go ahead and return my total sum.
Nice, this would be my go to enter diversion.
4666.56 -> course, it's technically a breadth
first, and we'll give that a test.
4670.96 -> Nice. And here we have that solution. So one
thing to note, I think it's pretty important to
4678.16 -> be consistent how you implement these algorithms,
I swear possible. So you'll notice that I always
4683.12 -> am a fan of a writing my like processing logic for
a node. Here I consider like the processing logic,
4689.76 -> where I add the value of my current node into
my total sum. I do that processing logic,
4694.24 -> typically when a node leaves the queue, and not
when the node is added to the queue, and just ends
4701.28 -> up being less repetitive that way, for example,
I've seen some people write code like this,
4705.76 -> where it's like, Alright, well, you know, I guess
since I'm adding my left child into my queue,
4712.64 -> that means it exists. So not only will I push it,
but I'll add it so I'll do I don't know total sum,
4719.92 -> plus equals current dot left dot Val, right, so
I'm kind of adding the child's value as soon as
4728.8 -> it's added to the queue. And you can write
something symmetric for the right hand side,
4733.68 -> you can see that because of this, I kind
of have to double up all of my code,
4738 -> which does not make it super clean. And I think
something that is even worse than that is well
4746.96 -> now you actually never added your root value
into the your, your total sum. So you'd have
4752.48 -> to begin your total sum as root dot value at this
point, I'm like, I kind of just hate this code,
4757.04 -> right? So you can run this, this would probably
work. So this code totally works, but it's not
4763.28 -> what I think is the best design for this pattern.
So I'd rather write it like this, right? consume
4769.52 -> your values when they leave your queue because you
know, eventually, everything's gonna leave, right?
4777.04 -> So I'll prefer it at least like this. Cool.
So before you go on to the next problem,
4784.4 -> recommend you practice both versions. I
know of this problem. So do it recursively
4788.48 -> do it iteratively have them both down pat because
we're going to increase the difficulty right now.
4797.92 -> Hey, programmers, Alan here right now.
One To go over the approach for this
4801.44 -> tree min value problem. So just like we've been
doing as of late, we're going to have to take in a
4806.48 -> binary tree as input into our function. And
we want to do is figure out what the smallest
4812 -> value within the tree is. That is we want to find
the minimum value. So we can totally assume that
4818.24 -> the tree is going to be non empty, right? And
so given that information, looking at this
4823.28 -> particular tree example, it's pretty plain for
us to see that the smallest number in the tree
4828.32 -> is just this three. Alright, so our function just
needs to return of the number three. So it's plain
4833.92 -> to see that the answer is three. But how can we
come up with an algorithm to do this for us? Well,
4838.32 -> we should look to our tools in our binary
tree toolbox. And that would mainly just be
4842.24 -> either a breadth first or a depth first traversal.
One obvious way to solve this one is to use either
4847.12 -> a depth first or breadth first iterative piece
of code that does a traversal and travels through
4851.68 -> the tree, then you just need to maintain some
outer variable to track the current minimum.
4857.12 -> And whenever you hit a node that is smaller
than your current minimum, then you replace
4862.16 -> that minimum variable. And by the end of
the code, you should have the true minimum.
4867.2 -> So the iterative version, I think, is pretty
straightforward. And I'll be sure to walk through
4870.32 -> that when we get to the code walkthrough. But for
now, in terms of our approach, visual, I think
4875.28 -> we'll step through this one recursively, right,
because it ends up being pretty succinct code.
4880.8 -> And so let's take a look at this tree. And
let's pretend that we filled in all of the
4885.12 -> null pointers, like usual, right? So these dark
nodes over here represent nodes that don't exist,
4890.08 -> meaning that there are no, right. So for example,
if I look at the three node, its left child is no,
4895.28 -> but its right child is 12. And that's going to be
very useful for us to at least visualize because
4900.64 -> I should make a base case about those null
nodes, right? So I know in the long run,
4905.12 -> what I want to do is figure out what the smallest
value within the tree is. And so a great default
4911.12 -> value for our null nodes would be to return
infinity. And here's the reasoning why I know
4916.64 -> that I should not really consider any of the
actual null nodes. And so if I have them return
4922 -> positive infinity, I know that positive infinity
is definitely not going to be the minimum
4927.12 -> compared to any numbers that are actually
within the tree. So we'll start to do is
4932.16 -> just fill in all of these infinite values.
In other words, every time we call upon a
4937.12 -> null node, or a null pointer, we're going to
return infinity. So I'd fill all of these in.
4942.08 -> Now using those infinities as our basis, we
can actually construct our return values.
4947.04 -> So looking at this for node to the left, what I
have to do is consider both of its children that
4952.48 -> it received, right, and also the value within
the current node. And so what I do is I check,
4958.24 -> alright, compared between infinity for an
infinity, what's the smallest value among
4963.2 -> them? Well, I know positive infinity is a very
large number. So really, the smallest number here
4968.08 -> should be four. And so this call should return
four, right? This node should return for
4973.76 -> similar story for this 15 node. Once I have
my left and right return values ready, I do
4978.56 -> a comparison with those values against myself,
right? So I check, what's the minimum among
4983.92 -> infinity? 15 and infinity, the minimum is 15. I
think it's gonna interesting now that we're at
4989.92 -> evaluating this 11 node, right? Now I have some
actual numbers. And so I do this comparison,
4994.56 -> right? I compare my left subtree value, which
is four and my right subtree value, which is 15.
5001.12 -> And also myself, which is 11. So among 411, and
15. What's the smallest number? Well, that would
5007.76 -> just be the four, right? So this node should
return four. And if I do a quick spot check,
5013.52 -> this makes some sense, because I have this answer
for above the 11 node, that's telling me that,
5018.8 -> within that subtree rooted at 11, the smallest
value was four, which is totally correct.
5024.48 -> Now we'll just go ahead and valuate the rest of
this tree. Looking at this 12 over here, I know I
5028.72 -> can't evaluate the three because I need a value on
the right hand side ready. So I must evaluate this
5033.6 -> 12. And I just do the comparison, right? What's
the minimum among infinity 12 and infinity? Well,
5038.8 -> let's just definitely 12. Finally, at this three
node, I take the minimum of infinity three and 12,
5045.2 -> the minimum there is three. And finally at the
ultimate root, I do the comparison. And I check
5051.52 -> what's the smallest among four, or five and
three? And the answer is going to be the three,
5057.44 -> right, which is exactly what we expected. And so
just by adding a little variation to our classic
5062.64 -> depth first recursion, we can totally solve this
problem. The logic we need to use to combine
5068.64 -> our child sub solutions into our main solution
is to just do a comparison, right? So overall,
5075.2 -> at every point of this tree, we asked ourselves,
right, given the smallest value in the left
5079.84 -> subtree and given the smallest value in the right
subtree. I compare those to myself, and return the
5086 -> smallest among those three. And then when it
comes to the complexity of this, it's pretty
5090.24 -> straightforward. We'll go ahead and say that n is
the number of nodes within our input tree. And we
5095.36 -> know that we're going to have a call for every
node of this tree. So that seems to be an O of
5099.6 -> n time. In terms of the number of recursive calls,
right, and we know within any particular recursive
5104.8 -> call, it sounds like we're just going to do some
conditional logic, right, just find the minimum
5108.8 -> among three things. Since three is a constant
number, I'm pretty sure that we're going to
5113.44 -> have just an overall time complexity of O of n,
considering the number of calls that we make.
5118.96 -> Now, that being said, we'll also have O of n
space complexity adjust due to the call stack
5124.16 -> that we use for baseline depth first traversal.
And that seems to be an optimal solution for this
5129.68 -> problem. Because what we'll do, we'll go ahead and
code this one up, and I'll catch in the next one.
5136.56 -> Hey, programmers, Alvin here, right now I want to
go over a JavaScript solution for this tree min
5141.68 -> value problem. And of course, we'll solve this
one a few different ways. I think I'll start by
5147.52 -> showing y'all maybe some iterative solutions. And
so we'll just do some classic depth first and also
5152.88 -> breadth first, along the way, right. So you know,
you're going to need to iterate or hit every node
5158.56 -> within your binary tree. So just go ahead and set
up either a stack or a queue. So I'll choose to
5164.16 -> start with a stack over here. So I'll say Kant's,
stack equals empty. And one thing I'll have to be
5170.4 -> aware of is looking at the assumptions in the
problem, they tell us that we can assume that
5175.2 -> the input tree is not empty. And so that means I
won't need to add a leading if statement checking
5179.28 -> if the top level root is null. So I can just go
ahead and initialize my stack with the root node
5184.72 -> inside. Cool. And then from there, you need your
main loop to iterate through the different nodes.
5191.6 -> So I'm going to loop while my stack is not empty.
So all stack dot length is bigger than zero. Cool.
5198.72 -> So if that's the case, and there are still some
nodes to visit, and begin a single iteration of
5203.2 -> this algorithm, let's say depth first, by doing
stack dot pop, so I removed the top of my stack,
5208.24 -> go ahead and call that my current. And then
from there, of course, we need to check
5213.44 -> if our children exist. And if they do, I'll
add them to the top of my stack, right?
5217.84 -> So I'll write a pattern like this, I'll say if,
let's say current dot left, that is not equal
5225.28 -> to No, then I can go ahead and push that existing
child on the stack, right? So stack dot push,
5232.16 -> and I'll push current left retinas a few times by
now should it be second nature, I'll do some same
5239.28 -> code for the right hand side. And this is kind
of my baseline of a depth first traversal, right.
5245.2 -> But as I look at this current node and its value,
I want to by the end of my loop, have access to
5252.08 -> the minimum value within the tree. And so because
I need to find the minimum value in this function,
5259.84 -> we're going to use a variable that I'll update
over time, right to track the current smallest
5264.72 -> thing I've seen. So I'll initialize this as let
smallest, I'm gonna have to think about a good
5269.52 -> default value for this. And so I'll go ahead and
initialize this to actually positive infinity.
5275.36 -> So if you're unfamiliar with some JavaScript,
infinity is basically just a number that is
5279.84 -> guaranteed to be bigger than all other numbers,
except for itself infinity, right? And the reason
5285.44 -> I'm choosing a big number, like positive infinity,
for my default value for the smallest variable,
5291.28 -> is because when I see any actual values of my
tree, I know they're guaranteed to be less than
5297.6 -> infinity. So these numbers would replace my
infinity, just gives me a good initial value,
5303.76 -> right? That's a pretty common pattern, right?
If you're looking for the minimum thing, and
5307.04 -> typically your default value is positive infinity.
If you're looking for a maximal thing, then your
5311.44 -> default value might be zero or negative infinity,
depending on the problem you're trying to solve.
5316.64 -> And so with that default value, where do I
actually want to replace it, right. And I'll
5321.44 -> choose to do that right after or something leaves
my stack. That way, you only have to say it once.
5326.08 -> If I wrote it, when I added my children into
the stack, what I'm saying twice, right,
5329.76 -> which is kind of annoying. So I'll just check,
hey, if current value, so be sure to compare the
5334.96 -> actual number value, current value is less than
the smallest, then I've just found a new smallest,
5341.28 -> right? So just replace that variable with current
value. Of course, by the end of our while loop,
5348.96 -> we should just return that variable, right? And
we should have the true minimum. So let's give
5355.68 -> that a shot, run these test cases. And this
is our rendition of an iterative depth first,
5361.28 -> right? Awesome. So if you wanted to switch it
up, you know, writing the breadth first is super
5368.4 -> trivial in terms of the change we make, you can
just make sure you do stack dot shift, right,
5374.08 -> because that would remove the front element
of your queue now and if you push then you're
5379.2 -> still adding it to the back. And I guess you
should probably rename this guy to queue.
5384.16 -> So very minute difference. Well,
tests that just give that a go.
5391.28 -> Cool, passes all of them. Nice. And one thing
to note. So Alex in JavaScript, there is no
5397.6 -> immediately when I recorded this video, there
is an immediately available, like optimal queue
5402.48 -> data structure just baked in, like you can't
import it through a standard library. And so
5407.44 -> when you actually do the array dot shift method,
that line itself is going to run an O of n time,
5413.52 -> right, because if you remove the front element of
an array in JavaScript, it will have to actually
5417.76 -> shift all the other elements over one position.
In other words, index one becomes index zero,
5423.6 -> index two becomes index one, and so on. And so
technically, if you implemented your breadth first
5429.36 -> exactly like this, just using a regular array,
and you shift out, then this would probably be
5434.32 -> technically like an O n squared solution, which
isn't the fastest, but we'll be able to pass
5440.4 -> the specs, typically n squared for most problems
is kind of okay. But you can avoid it if you want
5445.68 -> to get the blazing fast solution. But now let's
actually go ahead and implement my favorite
5451.44 -> version, which would be a recursive version,
right, which is technically of the depth first.
5457.44 -> Right? So we'll say const, trimming value,
chattering min value, dream and value. And
5465.52 -> to establish this one recursively will always
start with our base case, right? That's when
5471.2 -> you saw these curly guys. So I'll start my base
case, I'll say if my routes is equal to null,
5479.52 -> then that kind of means I have the empty tree,
what's like the minimum value in the empty tree?
5483.68 -> While that must be infinity, right? For
the same reason we chose infinity before,
5488.8 -> right? It's just a good default value,
because I'm going to minimize in the long run.
5492.56 -> Cool. And now what I want to do is I want to make
my recursive call. So if I call treeman value
5500.72 -> on my left child, and I call it on my right
child, I'll just think about what these
5507.36 -> function calls return. Right? Although they're
recursive, if these calls work, they should give
5512 -> me back the smallest value in the left subtree.
And the smallest value in the right subtree. So
5518.4 -> maybe, just to be clear, I'll go ahead
and save the system variables. So I'll say
5521.92 -> const, I'll say, left. Min. And also this
should be the right men, right? So I found
5530.4 -> the smallest in the left and the smallest in the
right. But I also need to think about myself,
5535.76 -> right? I am ru dot Val. So I need to choose the
smallest of root Val left men and Reitman, right,
5543.04 -> so you can write like a conditional. So just
some if statements If you want, I think the
5546.24 -> best way to implement this in JavaScript is just
to use the math dot min function. So JavaScript,
5551.84 -> you always have access to the global capital math
object has a few useful methods on it. One we're
5556.96 -> going to find useful right now is math dot min.
If you do that, you can pass in some arguments
5562.4 -> and an arbitrary number of arguments. So give
me the smallest between route dot Val and be
5567.2 -> sure to access the value because you
need to give numbers to men, right?
5571.28 -> Smaller between route dot Val, my left men and my
right man. Cool. And this feels somewhat similar
5580.08 -> to the approach drawn we did right where we had
to choose the smallest of these three numbers.
5585.68 -> So before we run it, maybe you're unfamiliar with
math dot min, I can quickly demo that for you.
5590.08 -> Let's say I had some numbers, we had 10, we
had three, we had six, and we had negative
5597.04 -> 12. And also 100. And if I console log with that
returns, I'll just run this file as a script. So
5606.88 -> I'm not going to execute the tests quite yet.
So I should get negative 12. Because that's the
5612.24 -> smallest perfect. And now I think we're ready to
go ahead and test this. So our recursive version,
5618.8 -> there we have it. Cool. Alright, so there, we have
our JavaScript walkthrough for this tree minvalue
5624 -> problem, recommend you practice all of these
different solutions, and then pick a favorite,
5628.48 -> maybe just have in your back pocket. That way,
you can always solve this problem in the future,
5632.4 -> right. So you should have no issue thinking about
how to solve like a tree maxvalue problem. And by
5637.52 -> now, you know, we're getting pretty comfortable
with trees. And typically, we're always going to
5641.36 -> fall back to either a breadth first or a depth
first traversal. But in the next few problems,
5645.84 -> we're definitely going to look at some spin offs
and some variations on how we can accomplish
5649.84 -> more complex logic using these algorithms as
our baseline. So I'll catch in the next one.
5659.36 -> Hey, programmers, Alvin here, right now want to
go over this max root to leaf path, some problem,
5664.48 -> pretty wordy title, let's take a look at what
this problem asks us to do. So we're going to be
5668.64 -> taking in a binary tree as input, and we want to
do is really talk about the paths within this tree
5675.92 -> in particular, root to leaf paths. So just to
review, we know that a binary tree typically
5681.28 -> for us has a single root and you can identify the
root by just looking at the topmost node, that is
5686.64 -> the node with no parent, right? And then also
given this tree there are three leaves, right?
5693.6 -> a leaf is a node that has no children. So do
bear in mind right a root has no parent. A leaf
5698.32 -> node has no children, some Like 11, and three in
this picture, there are neither roots nor leaves,
5703.84 -> right. So it could be the case that a tree has
many leaves, like this tree, right has three
5708.8 -> leaves. But a tree for us typically only has a
single root. And so what we want to do is consider
5715.84 -> all three of the different root to leave paths,
right, so you must start at the root, and you must
5720.72 -> terminate at a leaf. So one of those paths would
just be this one, right 511 for, what we want to
5726.48 -> do is consider its total sum. So just summing
the values within the nodes along that path.
5731.76 -> If I do five plus 11, plus four, that would give
me a total sum of 20. So that's just one of the
5737.36 -> possibilities. If I look at another path, let's
say this path of 511 to five plus 11, plus two
5743.76 -> would give me 18. That's another option. The only
other option is is final path from five to one,
5749.68 -> five to five plus three plus one. That gives me
a total sum of nine, right? And now among those
5756.16 -> three options, I want to choose the maximal path
some right? So that would be a final answer of 20.
5762.64 -> So in the long run, we need to come up with
some code that computes the maximal path sum
5767.84 -> from the root to any leaf. And that sounds like
a pretty hard problem, right? How can we go about
5773.92 -> doing that one? Well, hopefully you notice some
similar patterns, right to problems we've done
5778.96 -> previously. So just by looking at the name of this
problem, I'm reminded of a few different patterns,
5783.36 -> right? I can think of the tree some problem seems
pretty related here. And can I also think about,
5788.88 -> like that minvalue. Problem are, we had
some minimization logic, except now,
5792.96 -> I want to maximize something here. And so probably
what I'll have to do in this one is combined some
5797.68 -> of my previous knowledge to come up with a pretty
novel solution, but it's okay to rely heavily
5803.2 -> on our previous experiences, right. And
so let's start with something classic,
5808.48 -> I think we're gonna solve this one recursively.
And in the grand scheme of things, typically,
5813.84 -> for tree problems, that is, a recursive code
is usually your best bet when it comes to like,
5818.48 -> pathfinding things, right, and building pads and
determining pads. And so we'll take a look at what
5824.56 -> we should have our base cases be, if we're gonna
frame this one recursively. So they tell us that,
5830 -> all right, you need to consider paths, but
not just any paths, right? You always want to
5833.84 -> end at a leaf node. So the leaf nodes, like
the ending point, belief, notice the base case.
5838.96 -> So my base case is going to be literally about
a leaf node. And recall that that's a node
5843.52 -> with no children. So for example, let's say
we had a node as input that had no children,
5851.12 -> then what's the total sum of that leaf node?
Well would just be its inner value n, right? So
5857.52 -> kind of think about your base cases as if they're
their own inputs, right? As a quick aside, right,
5862.48 -> so a totally separate scenario, right? Now, let's
say I gave you a tree that contains only one node,
5868.32 -> and its value was 42. And I asked you to, alright,
tell me, what's the maximum path some of this
5874.32 -> tree, this tree is very small, right? If you
identify the root in this tree, it's just the 42
5879.2 -> node, right? Because it has no parent. And I've
also asked you for the leaves, there's only one
5883.12 -> leaf here. And it's also the 42, right? Because it
has no children, right? So the single note of 42,
5888.48 -> in this example, is the root and the leaf,
which means that the maximum path, some
5893.84 -> would just be 42. Cool. So I'm thinking about my
base cases as if they're their own inputs. Nice.
5901.04 -> And what you'd probably recognize here is, in this
scenario, we're kind of considering a base case,
5907.04 -> that is not about a null node, right, we will
need at least a separate base case that checks
5912.08 -> if we have an actual leaf node. And that's
very, very inherent and given in the problem,
5916.56 -> right? They say root to leaf path. Awesome. So if
that's the case, I'm just going to locate all of
5922.4 -> my leaf nodes in this diagram. And I know that
they're going to return the values within them.
5927.76 -> So just plugging those in, right? And now I can
start reconstructing on my higher level solutions,
5933.76 -> right? So given this 11 node, what decision does
this 11 node have to make to compute its answer,
5940.48 -> right? So let's read ourselves at this 11 node.
And we have to consider our left and right values,
5946.08 -> right. And so if i route myself at 11, the
four represents my max path sum through my left
5951.52 -> subtree. And the right hand side to now represents
the max path sum through my right subtree.
5957.28 -> Since I want to maximize here, the key
is to just choose between four and two,
5962.48 -> right? I choose the bigger of them, right? So
four is bigger than two, so I must use the four.
5968.08 -> And what I do is I take that four, and
I add my current value of 11 into it,
5973.2 -> and that gives me 15. And that would actually be
the answer for this subtree. In other words, I can
5978.16 -> check for correctness right now, if I root myself
at 11. I'm returning 15 to represent this path,
5984.48 -> right? I can either do 11 plus four, which
is 15. Or I can do 11 plus two, which is 13.
5990.56 -> Right and that 13 is smaller, so I won't prefer
it here. Cool. So so far, it seems like we're
5996 -> in good shape. Now let's take a look at another
node read to evaluate. Let's look at this. Three
6000.48 -> node. So it has a value on its right hand side,
right? It's receiving a one from its right child,
6005.68 -> but the left child doesn't exist, right? And
if you want to be a little more explicit,
6009.52 -> we know that the left child or three dot left is
going to be a null pointer. All right? So kind of
6014.16 -> plug that in here. And here's where we should
work in possibly another base case, sometimes
6018.64 -> it's very natural to course correct as we go.
And so for a null node, what should we return?
6024.32 -> Well, we know that whenever we have a null node,
it should never contribute to our final answer,
6028.88 -> we can kind of just ignore it, I guess, we want
to make sure that it's compatible with the rest
6033.76 -> of our internal logic. So bear in mind in this
problem, I want to take the maximum right? Recall
6040.56 -> from our previous problem, right, the min
value problem, we want to take the minimum.
6044.88 -> And so we made our null nodes return infinity,
right? Because if I want to find the minimum, and
6051.28 -> my null nodes, return infinity, by default, I know
that infinity is never going to win a comparison,
6057.6 -> right? Because infinity is very large. And we
just want to flip that logic over here, right?
6062.24 -> So because in the long run, I want to find
the maximum, I'll make my base case for
6068.48 -> the null nodes return negative infinity, right?
Because I know negative infinity is never going
6073.92 -> to win any contest where we compare things,
looking for the larger of the values, right?
6079.68 -> So for this null note, I'll plug in that
negative infinity. And now I shouldn't be
6083.68 -> able to do the same business logic as before,
right? So I'm rooting myself at the three node,
6088.48 -> and I can look at the results I get for my
children, right. So between my two children in
6093.28 -> my left path, I get a negative infinity, or in my
right path, I get a one, and I choose the maximum
6100 -> between them, right? One is bigger than negative
infinity. So I should use the one, right. And
6105.52 -> what I do with that one is, I add my current value
of three to it. So three plus one gives me four,
6110.88 -> right. And that makes some sense, because if
I look at that small subtree, rooted in three,
6115.84 -> the biggest path from root to leaf, or sub
root to leaf, I would indeed be a four. Nice,
6122.24 -> and now we have ourselves at the ultimate root
over here, I do that similar comparison, right?
6127.92 -> I check the bigger of my two children, so I'm
going to keep the 15. But then I add myself to it
6133.04 -> giving 20. Like we said before, this 20 logically
represents this path of five plus 11 plus four.
6140.8 -> Cool, so there we have it. And if you want to take
a look at the complexity of this seems nothing
6145.76 -> unusual. So we're going to have n as the number
of nodes, we're going to have O of n runtime,
6151.92 -> because we're going to have to make a call a
recursive call that is for every node within
6156.08 -> the tree. And if I think about any particular
call, we're going to make a foreign node,
6160.8 -> we're just going to do a comparison, right, I just
choose the bigger of my two children. So we're not
6165.6 -> going to have any, any loops within our calls, I
believe. Cool. So it just seems to be O of n time.
6171.84 -> Like we always say space complexity is O of n,
just due to the call stack. Nice. So let's go
6177.76 -> ahead and code this one up. And it should feel
like a combination of our previous tree some
6182.48 -> problems, as well as some a min value max value
logic. Hey, programmers, welcome back, Ryan,
6191.76 -> I want to go over a JavaScript solution for this
max root to leaf path, some problem. So this is
6197.84 -> going to be a pretty interesting tree problem.
And we'll jump right into the code, please make
6202.56 -> sure you watch the approach video before this.
So I think should be all primed up with the logic
6207.68 -> that we want to implement here. Right? And so
we'll start by doing this recursively. And I'd
6213.44 -> say that's probably the best way to solve this
one. So I think it's the only way I'll show you,
6218 -> when I want to do is start with a base case,
right? So we said we want to figure out our root
6224.4 -> to leaf paths. So our base case should be about
whether I have a leaf, right? So I'm going to
6230.24 -> go ahead and check let's say, if my root left is
equal to No, right? And root, right? Is equal to
6239.6 -> No, right? That's the definition of a leaf. So if
I have the left child and I have the right child,
6244.8 -> then I should return the value stored at this
node, right? So root, dot Val. Nice. So again,
6253.6 -> we're kind of emphasizing here is that base
case catches a scenario. If we're at like four,
6258.48 -> right, we have no children. Nice. And we will need
another base case in the long run. For now, let's
6265.28 -> say we left it like this, right? So we said that
in the context of solving this one recursively,
6271.68 -> the decision we make at every note is I choose the
bigger result from my left column A right call,
6277.52 -> and then I add myself to it, right? So I know I'm
going to do this recursively so I'm going to call
6281.52 -> the same function. And right now you should be
familiar with all right, you call your function on
6285.92 -> root left, and also root right? That I think about
what those calls return, right? They give me back,
6292.24 -> the max pass some through my left subtree
on the max path, some through my right
6296.4 -> subtree I just want to choose the
bigger results between Windows two.
6301.44 -> So no I swear to you saw me use the math dot min
function here I'll use the math dot max function.
6308.56 -> And I know that these calls these expressions
evaluates to numbers. So I can actually just
6313.52 -> pass these guys in, in line. So I would just
move this up like that. So when finding the
6319.04 -> max between these two results, and I'll
go ahead and call that we'll say, the
6328.16 -> max, your child, right? Maybe I'll write
this online, they prefer. And then from
6335.12 -> there, I just add myself to that max
child, right? So I'm going to return
6339.12 -> route dot valance myself, plus max child. And
we'll call that max child path. And that should be
6349.68 -> it except for one thing we're forgetting. So
take a moment, see if you can read between the
6354.8 -> lines here. And what scenario Am I missing? We did
mention it in the approach video. So can you spot
6362.08 -> what is not present here? And that's something
I find I do often right? If I'm able to really
6367.12 -> come up with a nice, meaningful and consistent
picture, then everything I drew in the picture
6372.16 -> should translate to some piece of code over here.
Let's give it a shot. Expect to fail this one.
6380.88 -> See what we get? Yeah, so we're getting an
error cannot read property left have no,
6385.92 -> right, I found on the very first example.
So I'll tell you that this is caused by an
6391.52 -> asymmetric node, like this four over here,
right? This four has no left child. So imagine
6398.08 -> what would happen in this instance,
right? So if we're evaluating this code,
6402.96 -> we know that our route is going to be this
four node. And this if statement on line 10,
6408.08 -> is not hit, right? Because four is not a leaf,
right? Because it has a right child's right
6414.48 -> child does not know. So instead, it's going to
run until 11. And it's going to try to execute
6419.6 -> max path, some of root dot left root that left is
no. And so when we actually evaluate that call,
6426.16 -> now we're seeing is no, and we're gonna check
no dot left over here. And that's going to break
6432.08 -> right? It's exactly the line that's broken.
And so in addition to this base case, right,
6437.92 -> when we bought him out at a leaf node, what if we
just end up at a null node, so if root is null,
6444.24 -> then we said that a good value to return would be
negative infinity, right? Because I'm choosing to,
6452.32 -> in the long run, do like maximal logic and want to
pick the max. So if I choose a negative infinity,
6457.52 -> that won't interfere with any of us taking a
max, right? Because imagine that this thing
6462.8 -> was negative infinity. And I would just prefer
the right hand side if it was not infinity,
6467.44 -> right? Negative infinity that is. And so
with that, let's go ahead and give this a go.
6477.44 -> Cool. And then we have a nice solution
for our max root to leaf path some
6481.84 -> problem. So notice how short the code is,
by no means do I think this is simple code,
6487.2 -> though, right? At this point, it's okay if it
feels a little tough. But you understand how we
6492.4 -> have some familiar patterns, right, I still
have those two recursive calls right over
6496.24 -> here. And we typically only vary in how we take
those recursive calls or the results from them,
6502.08 -> and combine them into our higher level answer. So
keep practicing this problem and I'll catch you
6507.76 -> in the next one. All right programmers. That wraps
up our course on the introduction to binary trees.
6512.48 -> If you want to explore this binary tree topic, or
really any other data structures and algorithms
6516.64 -> topic more deeply. Be sure to head destructing
dotnet where we have all of these topics covered
6521.68 -> through tons of problems where we have video
walkthroughs and illustrations for every single
6525.84 -> problem. I think you'll find this especially
useful if you're repairing and really cramming
6529.28 -> for those technical interviews. Thanks
for watching, and I'll see you there.
Source: https://www.youtube.com/watch?v=fAAZixBzIAI