Skip to main content
Loading Explore guides…
Binary Tree Fundamentals · Acedra
Home
Explore
Computer Science
Binary Tree Fundamentals
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
47 segments
Copy
Hide video
0:00
All right we are back all right so today what we're going to do is we're going to go over our binary tree fundamentals and yes I know maybe you're already familiar with this but my goal is to make this channel one of the world's largest resources for software engineering interviews and this kind of preparation so the key is we have to go through our fundamentals and get them very solid before we can build on top of them and do other topics so if you haven't subscribed
0:28
to the channel subscribe to the channel and like this video what we're going to do today is we're going to talk about our fundamental traversals of binary structures binary tree structures and we're going to talk about the types of trees we're just going to go over our very basic concepts so that we have them very sound so let's go over three of the key kinds of trees or three terms we can use
0:51
to describe a tree if we have a tree where leaf nodes have no children or a node has two children it is a full tree notice this is a leaf it has no children this is a leaf it has no children this is a leaf it has no children and that is the leaf it has no children but the nodes that do have children have two children they cannot have one chip child they have to have two children so this tree is full every time we decide to have a descendant we have to have two descendants we
1:26
can't just have one so this node decided I'm going to have descendants I need to have to this node said I'll have no descendants it has no descendants no children that is a full tree and you can tell by what it looks like so this is a complete binary tree complete binary trees are our binary heaps we make binary heaps complete trees so what does complete mean all it means simply is when we fill out the nodes we go top to bottom we go left to right do you see how we go and fill it
1:58
out like this do you see how we go top to bottom and do you see how we go from left to right and if I just put a node right here just out of the blue I stuck a note in there this tree is no longer complete because because I just missed putting a note there so this is a complete by an area and then finally we have our perfect binary tree so a perfect binary tree is where all the leaves are on
2:20
the same level and all of the nodes that decide to have descendants have exactly two children a perfect binary tree is both complete and it is also full you see how the notes that decided to have children decided to have descendants they only can have two children they can't just have one child but the ones that did not decide have no children and notice how all of the ones that did
2:42
not decide what we call leaves are all on the same level this is a perfect binary tree so now that we understand our terminology very soundly what we need to do is let's look at the traversals and yes these are going to be the rock reversals you can do on a tree but it's very key to understand these traversals so we can adapt them to other problems if we were very flexible with traversing
3:07
a binary structure it becomes much easier to solve problems recursively or iteratively with a stack so let's look at our traversal now okay so what we're going to do is we're going to do a traversal of this tree and there are three fundamental ways to traverse a binary tree you can do it other ways but these are the three key ways there's your pre-order traversal your inorder traversal and your post order traversal and I don't want you to worry about the part in the word where it
3:39
says order I only want you to notice the first part of the word notice how it says pre notice how it says in notice how it says post that prefix the prefix to the name of the traversal tells us when we visit the node we're sitting at so what I want you to see is in a pre order traversal in a pre order traversal we visit the node we visit the left subtree we visit the right subtree do you
4:07
see how it's called pre order do you see how the N is the first visited you see how it's pre before the left and right so for inorder think of it as in so left subtree visit the node and then visit the right subtree so it's you see how it's in do you see how it's in the that's how you remember in order traversal and then we have our post order traversal we go left sub-tree we go right subtree
4:33
we visit the node so do you see how it's post it's after the left and right so the left and right stay in sequence left and rights and sequence but the the prefix tells us when we visit the node before the sub trees the sub trees will be left to right but when do we visit the node that's what the prefix tells us so what we're gonna do is we'll do a pre-order we'll do an inorder and then we'll do a post order traversal here so this is what I want you to think about when we're
5:02
traversing a tree I'm going to write something that's going to help you so I want you to think of recursion think of recursion as a certain policy we have to execute at each node think of the recursion as the tasks we need to do at a node and the state this state stays on the call stack this is the key with recursion so do you see how I just put node left to right this is our pre-order we're
5:28
doing pre-order right now and what we want to do is we want to execute the policy at each node so what we do is we start at the 10 I see I have to do a node visit I have to do a left subtree visit I have to do a right subtree visit so what I'm gonna do is I'm gonna do the node visit I'm gonna just output 10 and what I'm gonna do is I'm gonna erase the end so I'm just familiarizing you with the example that we're walking through and notice we don't just have to print a node we can
5:55
do any form of work the whole point is visitation we want to get our fundamentals down for visiting a node right now so what we're going to do is we're going to execute our policy at this stack frame we're going to say I need to visit my left so this stack frame says I need to visit the left subtree so we're going to circle the left okay so now we recurse and now we just circled the left
6:19
and now we're gonna come down and we'll come to the 7 what is the policy at 7 7 says ok what do I need to do here in my stack frame so what we see is we see that 7 has 2 we see that 7 has to do we see that 7 has to do a node visitation so what we're going to do is we're going to visit seven and notice the next step in sevens policy in this stack frame is to visit the left subtree so let's do it so we visit the left subtree and now what we need to do is we need to do this policy
6:53
at this stack frame so do you see how recursion is we're executing the same policy at each node but it's going to give us the behavior we desire because of the way we're ordering the visitations right so what we're going to do is we'll visit the six and then we're going to recurse and then we're going to come to the one we're going to visit the one and then one says I need a visit my left
7:13
subtree we hit a base case nothing we come back one says okay I finished my left so I can erase that I'm done and then what is one's policy what is the policy at this stack frame what is left for this recursion in this stack frame to finish and we see all that's left is visit the right subtree let's visit the right subtree and then we see that there's nothing so we come back and now one has
7:35
nothing to do so now we return to our call and now 6 says okay thank you left subtree you're finished now what is next in sixes stack frame and like again I say stack frames but the thing is we don't have to use the call stack we could make our own stack we can make our own stack and then we could execute the traversal that way so it just depends on the traversal and what implementation you want
7:58
to do so this says I need to visit my right so the six visits is right there's nothing there so six comes back so now six has nothing to do it returns to its caller seven in sevens stack frame in its policy its stack frame it says I visited my left and now all seven has to do is visit its right subtree there's stuff to do over here so let's do that so now eight says what do I need to do what
8:22
does eight need to do it needs to visit itself it needs to visit its its own node and then it needs to go left we see there's no left and then eight says okay I need to go right now so we recurse on the right subtree and now we're at nine what is nines policy what is nines job and I want you to drill this in your brain because this is how we really understand recursion this is how we really
8:42
see that recursion expresses our decisions at each node it's different for each node each node has a different state do you see how states differs this is recursion fundamental I want you to internalize so we see nine so what we need to do is we need to print nine we see it has to print itself and so nine needs to visit its left nothing nine needs to visit its right nothing so it has nothing left
9:05
if we return to the eighth the eighth finished its right subtree nothing left it has nothing to do left and now we come back to seven seven was just visiting its right subtree seven says okay unfinished seven is finished and now we return to ten and do you see how this all was the left subtree of ten do you see how our next task is to explore the right subtree of ten so all the traversals do is they change how we traverse this tree they change when we visit nose what we do is
9:33
we check the right subtree and then what we need to do is we need to print 11 because 11 has that task to do and so 11 has to visit its left there's nothing here so we come back to 11 and so 11 has to visit its right and so 11 visits its right and now 20 comes to itself and 20 says what do I need to do here I need to print myself go left and right so 20 will print itself so 20 now needs to
9:56
go left so it comes to 1440 needs to print itself and now 14 will go to the left so 14 finds nothing it'll go to the right as well it'll find nothing and now back to 20 what was 20 just doing it was looking to its left so what we're going to do is we're going to finish that what is the next state in 20 stack frame well we need to go to the right we come to the right and we see 22 so we see 22
10:21
and 22 s job and well it hasn't printed itself it hasn't gone left hasn't gone right it needs to do its job so we're going to print 22 and then it will go left there's nothing and then we'll go right there's nothing 22 is finished it returns to 20 and then 20 has explored it's right LLL finish 20 has nothing left to do LLL return to 11 11 has finished this right so 11 has nothing to
10:42
do it's going to return to 10 10 has finished it's right and 10 stack frame the top level stack frame that drove us into the recursion is finished we're going to return to our caller whatever we returned whether it's the count of the nodes or something and that is finished that is the traversal of the tree this is what the pre-order traversal looks like the key is you don't really need to memorize
11:03
these traversals you literally get the hint of what they are from the name anyway I think you get the idea now let's go through the in order and post-order and see how those work out they're basically the same thing so now what we're going to do is we're going to do an inorder traversal and all that changes is we're going to do a different policy at each node so let's define that policy okay so now all we did was define a different policy so we're going to go left we're
11:33
going to visit the node we're sitting at and then we're going to go right that is all that we're going to do different so what we're going to do is we're going to start at the 10 the 10 will be called by an external caller and we're going to kick off our recursion what we're going to do is we're going to execute the policy at 10 and when you really do internalize this that recursion at each frame every frame has a different state although every frame has the same policy every
11:59
frame will have a different state at different points in the recursion so we're going to go left in 10 and then we come to 7 what does 7 need to do 7 needs to go left what will 6 do 6 needs to go left what will one do one needs to go left and one is going to go left there's nothing there it comes back and so what does one need to do one needs to print itself so one printed itself and
12:22
after a prints itself it needs to go right there's nothing there and now what we need to do is come back we come back to 6 because 1 is finished we come back to 6 so 6 just finished up going left so now 6 needs to print itself so now 6 needs to go right we see that there is nothing - 6 is right so what we're going to do is we're going to just return to 7 we have nothing else to do at 6 so 7
12:46
just finished going left so 7 its next job in its stack frame is to print itself so now 7 needs to go right and now 8 needs to go left we see in its stack frame that's his first job and then it goes left it finds nothing and then 8 needs to print itself and then 18 needs to go right and then it goes right and then we see 9 needs to go left there's nothing there 9 needs to print itself and then 9 needs to go right there's nothing there 9 has nothing to do it returns to 8 and 8 has
13:17
finished its right subtree a has nothing to do left so eight returns to seven seven is finished is right sub-tree so seven returns to ten ten has finished its left subtree all that work we were doing was on the left subtree so now ten needs to print itself and now ten needs to go to its right and now eleven needs to go to its left there's nothing to eleventh left it needs to come back
13:39
to itself and now eleven needs to visit itself and then eleven goes to the right twenty what does it need to do it needs to go to the left fourteen needs to go to the left there's nothing there fourteen needs to visit itself and then we see fourteen needs to go right there's nothing there so fourteen returns to whoever called in which was twenty twenty is done going left twenty needs to
13:59
visit itself nest and then twenty needs to go to the right and then we reach twenty-two twenty-two needs to go left to visit itself and go right so it goes left there's nothing comes back it needs to print itself and now twenty-two needs to go right there's nothing there we return to 20 20 is finished twenty returns to its caller its caller has finished its right subtree 11 returns to its
14:21
caller ten ten has finished its right subtree and we are finished printing it and I wouldn't even notice there's something special about this what we just did there's something special right here because do you notice how these are in increasing order this tree is a special kind of tree called a binary search tree so the nature of the way these notes are oriented is this node is in the
14:42
middle of all of these guys and all of these guys so if we go to the left we go lesser in value we go less than ten everything in the left subtree is less than ten everything in the right subtree is greater than ten so this is a special kind of tree again a binary search tree you're probably already familiar with this if you are watching this but anyway so now I think you really get
15:02
the idea but just to drill it in let's do the post order traversal okay so now we're going to do the post order traversal and nothing changes nothing changes except our policy at each node the way we visit the nodes so let's just go straight through this and you should be pretty rapid with this now so what we're going to do is we're going to go to the left first for Ted we'll go left first and
15:26
then seven we'll go left six we'll go left this is starting to look like the in order traversal but let's continue so one go to the left we go to the left and we see that we don't find anything so we come back and this is the way this differs from our in order traversal instead of visiting ourselves next the next task is to visit our right subtree remember this is a post order traversal we
15:51
visit ourselves a post last right so what we're going to do is visit our right there's nothing there and then we'll visit ourselves and what we're going to do is Prince ourselves there's nothing left to do it one so what we'll do is return to our collar six so six needs to go to the right there's nothing there so we come back and so six needs to visit itself so we print six six is finished so six returns to its collar we see its collar was seven seven just finished up its left
16:19
subtree so now seven goes to the right seven goes to the right and we come to eight what does eight need to do it needs to go to the left to the right and to itself so we go left there's nothing here so we come back to eight so eight now needs to explore it's right and so now eight is exploring is right we come to the nine so nine needs to explore its left there's nothing there so now
16:41
ninety needs to explore its right there's nothing there so now nine only needs to print itself nine returns to its caller eight eight realizes it's finished its right subtree and now eight needs to print itself it has nothing left to do it returns to seven seven all it needs to do is prints itself seven has nothing left to do it returns to its caller ten ten finished its left subtree all it
17:04
has to do is go right and now we come to eleven eleven needs to go to the left eleven does not have anything on its left so 11 goes right we come to twenty twenty needs to go left to right and visit itself we go to the left we come to fourteen we go to the left there's nothing we go to the right there's nothing we visit the node fourteen that's the last task in our stack frame we visit 14 we come back to 20 20 is exhausted its left subtree so twenties next task is to go to the
17:31
right so now we're going to go to the right we see 22 22 s job is not to print itself it's to go left to go right and then print itself so now 22 is going left so there's no from there it needs to go right there's nothing there it needs to print itself now we come back to our caller 20 it's finished exploring its right subtree now 20 needs to print itself 20 is finished with its tasks so it comes back to 11 again Levin realizes I'm done with my right subtree 11 needs to print
18:00
itself now and now 11 has nothing to do we return to our caller and now we have 10 10 realizes I'm done with my right subtree and now finally 10 prints itself 10 realizes it has nothing left to do and we've completed our traversal that is our post order traversal that is basically how you do it see the thing is you don't always have to do this recursively but what we're going to do is there's a certain way we need to visit these nodes and however we structure our recursion how
18:28
every structure our are stacked what items we push and in what order is going to change how we visit these nodes it's not that scary to deal with binary structures binary tree structures because as long as we know our fundamentals as long as we know how to visit nodes we can be very flexible in how we deal with these structures I haven't even gotten into breadth-first traversal we can do a zigzag traversal we would use a queue for that but that's for another video but I just
18:55
want to introduce this concept you're probably already familiar with this if we are thinking about complexities if we think about any of these traversals where we're touching all of the nodes if n is the number of nodes then the upper bound we can set on the time we're taking is going to be linear time we're going to scale in a linear fashion as our tree gets bigger if we're touching all of the nodes anyway we're going to get more familiar with tree complexities and all that it
19:19
gets fairly straightforward as you do more problems but that is all for this video if you liked this video hit the like button subscribe to the channel this was a very basic fundamental one of course we have a table of contents so you could skip through this I would do not expect anyone to watch all of this but that is all for this video and what I'm gonna do.
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat