Binary Tree Bootcamp: Full, Complete, & Perfect Trees. Preorder, Inorder, & Postorder Traversal.

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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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   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.

Channel: Back To Back SWE

Views: 188,274

Keywords: inorder traversal, binary tree, binary trees, preorder traversal, tree traversals, full binary tree, complete binary tree, perfect binary tree, postorder traversal, Back To Back SWE, Software Engineering, computer science, programming, programming interviews, coding interviews, coding questions, algorithms, algorithmic thinking, Google internship, Facebook internship, software engineering internship, swe internship, big n companies

Id: BHB0B1jFKQc

Length: 20min 0sec (1200 seconds)

Published: Sat Feb 02 2019