Binary Tree Level Order Traversal - Drawing The Parallel Between Trees & Graphs

all right so what we're going to cover today is a Amazon interview question I heard this was on like phone screenings or something it is the level order traversal of a binary tree a binary tree you will have a little cool graphic there so first off if you have not subscribed to the channel subscribe to the channel and like this video my goal is to build one of the world's most useful resources for interview prep this is why I give every video a table of contents this is why I'm doing a video a day there are so many topics that are necessary for you to understand to pass a software engineering interview unless you just get the questions that you already know or you just know a certain set of topics and you get asked those topics but my approach is to just become a generally good computer science has become good at answering these kinds of questions so that when you're in an interview you know that whatever is thrown at you you have a decent ability to handle it so anyway today's question a level order traversal of a binary tree so what I have here is a binary tree and what we see is we have the traversal of the binary tree we see one two three four five six seven eight and how is that related to the way we traverse this tree as you can see we go level by level top to bottom left to right so 1 2 3 4 5 6 7 8 so I'm going to walk you through the way you should think about this or could think about this if you have never seen this question so whenever you get a question the first thing to start out with is what do I already know what do you already know when you're going into an interview if you even got in that situation in the first place you probably already know something you probably already know what a binary tree is you probably already know your preorder traversal your inorder traversal and your post order traversal you already know how to traverse a binary tree structure and I also did a video on the traversals and like it binary tree bootcamp thing so the first thing to start off with is tell your interviewer okay you're asking me to do a traversal maybe I've never heard of level order maybe I've never heard of these other things but I know how to do my basic traversals that is a stepping stone you have your foot now in the door to bring yourself to a greater understanding and so now I would ask you how do we traverse the tree level by level so first off I want you to make a mental connection this is where our knowledge of data structures come in and we realize that all trees are a cyclic connected graphs and an acyclic connected graph is a tree so if we have an acyclic connected graph it might not look like a tree it might look like this okay so this is the first mental leap I need you to make with me so what you see here do you see a graph or do you see a tree so what you see is actually both you see an acyclic graph you see a graph it has no cycles but it's also graph it has nodes with with edges but at the same time it's a tree because a tree is a a cyclic connected graph so what does that mean again remember a cyclic means no cycles and connected means that all of our nodes are connected and there's no disjoint segments over here this is all together in one one piece so what do you notice here is this different from what I showed you before and it's actually not different let me show you the levels of this tree and I really want you to notice what I'm doing right now here is level one this is our root this is the first level out from the tree and do you see how I'm saying levels now that we've drawn this mental connection we now know we have art graph fundamentals open to us we can do depth-first search or we can do breadth-first search but I want you to notice how I'm about to circle this graph so here's level one let's go out one more level here is level two let me show you one more level out let's see level three do you see how this is the third level out so we start a 1 1 2 3 1 2 3 1 2 3 1 2 3 so do you see how a tree is actually a graph and you see how we are going out level by level and now let's finish it off and do the final level the 4th level so now we see all the levels of our original tree and now that you understand that a tree is just an a cyclic connected graph now we have our fundamentals open to us and let's go back to our original tree and do exactly what I just did ok so now we have our original tree and now my job is I'm going to do the level by level analysis again and let's see if this is how we want to solve this problem so what is level 1 what is level 1 let's Circle it that is level 1 now let's look at level 2 now let's look at level 3 and now let's look at level 4 so do you now notice the pattern do you now know which kind of search we want for a level order traversal you see that we want to go level by level how do I go level by level in a graph I showed you the levels also a great resource is my video on depth-first breadth-first search so this is a breadth-first search this is the huge breakthrough you need to solve this problem the key to doing a level order traversal of a graph structure which a tree is a specific kind of graph structure is that we need to do a level order traversal do you see how each level is getting hit if this were a graph we would go out in circles but this is a tree so we're gonna go level by level we're still doing a level order traversal as if this is a graph while it is a graph as if it's a graph but it's going to do a level by level traversal so what do we use for a breadth-first search we know our data structures and we know a queue is what we use for breadth-first search and what do we use for depth first search we use a stack whether it is the call stack or it is our own stack we create it is all about the behavior that the data structure enforces a queue enforces first-in first-out a stack enforces last in first out so what I'm going to do is I'm going to walk you through how a queue traversal will happen and all we need is a queue we don't need a hash set we don't need a hash table of any sorts because this is going to not have cycles it's a cyclic it's a tree it's a a cyclic connected graph so what we're going to do is we're going to walk through our breadth-first search using a queue so let's start that right now okay so we have our binary tree here we have our queue this is the front this is the back and we have our output so our output has to be in sequential order so what we're going to do is we're going to begin our breadth-first search using a queue what we're going to do is we are going to add the roots to the search so add one to the queue and notice that I circled the one this means that it is the node we are adding a reference a pointer to the node of one we know we need to process it so after I add one the start node into the search I begin the search I enter the while loop again the code is in the description if you want to read that I have that for reference code is in the description as always it is always their description so what do we do we enter the while loop we look how large is the layer how big is this layer the size of the queue is one so this is how many elements we are going to process in this iteration of the while loop in this layer layer 0 layer 1 call it whatever you want is going to be the root so what I do is I first I pull this item and I print it so now you see one is output and what I do is I add its left and it's right child and the order matters I add the left before I add the right so I add two and I add three okay so now our queue has two and three so we knew we only had one item in the layer so now our next while loop iteration we now see how large is the layer it is two items long that is layer one that's the next layer so what do we do we're going to process two items we're going to process out these items so first we process the two let's print two and add its children to the back of the queue and you see that choose children are four and five and now we are done processing two and now it is three Stern and now we process three and now we add threes left and threes right child and that was the processing of two items we see that that is the layer so now our next while loop iteration what is the size of the layer that we just prepared for ourselves the size is four that is this layer and do you see how this is a layer this is so critical breadth-first search goes layer by layer it's literally like a circle and depth-first search goes deep it goes deep first it goes in in depth first and I have a video on depth-first search of searching a maze so that is a good example of depth-first search so we remove the four that is the first element to process and we output for and we add its left and right child all we do is add eight okay so five is next so we process five we just output five does five have any children and we notice five six and seven have no children five six and seven are what we are about to process so five adds nothing we're done with five and now we process six and again six has no children so we're done with six so seven let's process seven and finally 7 has no children so we're finished with this layer and now we go into the next inner of the while loop and we say how large is this lair I'm working with it has a size of one so what we're going to do is we're going to print eight ad Apes children we have nothing and nothing nothing is added and now we're done processing eight and now I come to the top of my while loop and I say what is the size of my lair well the queue is empty there is no size and I'm not even going to continue with the iteration because the queue is empty actually in the code it wouldn't even get to where it checks the lair size it would just see that the queue is empty and then we know the breadth first search is finished and what do we have here we have the level order traversal of our binary tree but in reality it's actually a graph it's a a cyclic connected graph and when you can make that mental connection in your brain it becomes simple because we unlock our ability to execute our fundamental searches so that is all for this video if you like this video hit the like button subscribe to the channel my goal is to make this one of the world's largest resources for software engineering interviews I don't know how large of a channel or resources will ever become but I'm going to try to make it as exhaustive as possible and give all that I know on this channel so that other people can learn and grow from it so that is all for this video and now we got to take a thumbnail photo because I forgot [Music]

Channel: Back To Back SWE

Views: 35,236

Rating: 4.9681816 out of 5

Keywords: level order traversal, binary tree, graph search, breadth first search, depth first search, level order binary tree traversal, binary search tree, tree, 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: gcR28Hc2TNQ

Length: 12min 55sec (775 seconds)

Published: Sun Feb 10 2019