This course has been updated! We now recommend you take the Complete Intro to Computer Science course.
Transcript from the "Depth-first Traversal" Lesson
[00:00:00]
>> Brian Holt: So pictured here is a valid binary search tree. Here's a link if you wanna go down and see the other one.
>> Brian Holt: So I've given you this tree, this data structure. I want you to serialize it. And when I say serialize it, I just want you to make it into something you can console log basically, right?
[00:00:20] Because I love console logging everything. [LAUGH] I want you to make it into a flat array. How are you going to do that? And we're gonna talk about four different strategies to how to do this. So, the first one, which I think, for me, is my natural way of thinking.
[00:00:36] That's usually where I like to start is what is the most human way to think about this and then I optimize from there to more computer optimized ways of thinking. I think of things in terms of depth-first traversal. And usually, I go with pre-order. That's just the way that my brain thinks about things.
[00:00:52] Because I wanna go as deep in the tree first, and then start serializing things from there. Pre-order traversal is I'm gonna add 8 and then I'm gonna process everything in the subtree, right? So I'm gonna add myself, and then I'm gonna add everything in the left subtree, right?
[00:01:06] Once I do everything on the left subtree, then I'm gonna do everything in the right subtree, right? So first, add yourself, then process left tree, then process right tree, right? That's pre order traversal. So I'm gonna add 8. Then I'm going to left subtree and I'm gonna add 3.
[00:01:24] And then I'm gonna go into left subtree of that, I'm gonna add 1. Then I'm gonna process everything in the right subtree of 3, right? So then I'm gonna add 4, 6, 7, 10, 14, 13, right? So if you look here, I basically go through all of these steps of what I said here, and you end up with 8, 3, 1, 6, 4, 7, 10, 14, 13.
[00:01:47] Right? Does that make sense? So yeah.
>> Brian Holt: I'm gonna say the word process node. When I say process node, it means you're gonna do whatever you're going to do, right? In our particular case of my example, you're going to add something to an array. That's the processing of a node, right?
[00:02:04] So you're gonna process the node, then do the left tree, then do the right tree. And that is preorder traversal, right? Now what you're left with here, 8, 3, 1. This is nonsensical in the sense that it's not a sorted list. Despite that fact that our tree actually does have order to it, right?
[00:02:28] That's what a binary search tree has, is it has order. So, what if I want you to print these things out in order, right? You might do what's called an inorder traversal, right? So, what you're going to do is you're going to process the, sorry, your gonna do the left subtree first.
[00:02:47] Then your going to process the node that your on. And then your going to do the right subtree, right? So I'm gonna go, start with 8 right? Because you always star with the root node. Then I'm going to process the left subtree, right? So I'm going to go down here to the left.
[00:03:01] Which is 3. This is one is going to go to the left subtree as well. And it's gonna go to 1. 1 has no left child, right? So it processes itself. Then it tries to process the right child, which again doesn't have a right child so it's just returns after processing itself.
[00:03:18] So, it goes back up to 3. 3 now processes itself 3, right? And then it processes the right subchild, so then it goes down to 6. Then 6 goes down to 4, 4 processes itself, goes back up to 6, 6 adds itself then it goes to the 7, 7 adds itself you go all the way back up here to 8, 8 adds itself.
[00:03:41] Then 10, then goes to 14, and 14 doesn't process itself yet. It goes to 13, then 13 does, and then 14. So you end up with [1, 3, 5, 6, 7, 8, 10, 13, 14]. You end up assorted lists, cool? Then you're probably getting like how these are different from each other we're gonna do post order traversal, which means that you're gonna do all the children first and then add yourself right?
[00:04:14] So 8, 3, 1,right? and then 1 has no children, so 1 adds itself, right? Then it goes back up here. 3 still does not add itself to the list. It goes down to 6, then 4. So 4 is going to add itself. Then 7, then 6, then 3, then 8.
[00:04:33] Then you go down to 13. Then 14 to 10 and then 8. So, if you go down here,
>> Brian Holt: so one thing is, when you're doing postorder, definitely a root node is always going to be the last thing processed. Follows right? Because it's gonna process all the left tree and the right tree and then add itself.
[00:04:55] So let's talk about when you would use any one of these. First of all, does anyone have any questions about these particular things?
>> Brian Holt: So it's just a matter of changing what order you're going to process the nodes in. That's the whole gist of the three variance of depth first traversal.
[00:05:20]
>> Brian Holt: Yeah, let's talk about when you would use these. So in preorder reversal, I thought I had. Right here, cool. So if you want a sorted list out of a BST, inorder traversal is exactly how you do that. That's almost why it exists. If you're trying to make a deep copy of a tree, so I have this binary search tree and I want to create an exact copy of it, that would be a really really useful time to use preorder traversal, right?
[00:05:52] Because you want to create a node, and then you want to add a left child and then add a right child, right? So that's when preorder would be really, really useful, because you can't add children to something that doesn't exist yet. So that's when you would need preorder.
[00:06:05] Now, imagine if you were trying to delete a tree. Well, if you try and delete something, and then go to find its children, because it's already been deleted, you couldn't find its children, right? So that's when postorder would be really useful. Because you would go delete everything in the left tree, rather, delete everything in the right tree, and then delete the node itself, right?
[00:06:24] So that's when a postorder traversal would be really, really, useful.