Traversals

[00:00:00]
>> So let's talk about the next most important point, which is gonna be traversals. We're gonna talk about this several times throughout the day, and the order of traversals makes a big impact. So I'm just gonna put out another tree right here, and we're gonna talk about the three traversals.

[00:00:15]
All right, I guess I should have just left it up, but what can you do? Okay, you can't win them all, 27, we'll do 10, 15, and 3. All right, so there are three types of traversals. There's a pre-order, which we will not do anything that requires pre-order today, I'm sure we could use something.

[00:00:35]
I'm sure you could do la module system with pre-ordering, I just don't know about it yet. Then we're gonna have in-order, and then, we'll do post-order. So what that means is that, there's really just three operations you do in any search in a binary tree, is that you will go down the left-hand side of the node.

[00:00:57]
You'll go down the right-hand side of a node, or you will visit the node. Right, like this right here is a traversal. This right here is a post-order traversal. Meaning that I'm gonna go down the left side, I'm gonna go down the right side, and then I'll visit the node.

[00:01:14]
So let's just pretend that visiting the node, adds it to a list, and we print out that list at the end of the traversal. So what does that look like? We'd start right here. What do we do first?
>> We go left.
>> We go left, okay? We go here, what do we do next?

[00:01:27]
>> We go left.
>> Left, all right, we go here, we go left, there's nothing here, so we go back up, we go right. There's nothing here, we then visit the three. We go back up, we go to the 10, we go to the 15, we go to its child, nothing there, nothing there, come back to the 15.

[00:01:41]
And then, we're able to say, hey, there's 15, then we go back up, we hit the 10, the 10 now has gone left and right, so therefore, we write the 10. We go to the 20, go to the 25, go to the 23, nothing, nothing, 23. Go back up 27, 27 has no children.

[00:01:57]
So therefore, we write that out, we go to 25, 25 now gets printed out, then we go to 20, 20 gets printed out. This is called a post-order traversal. This should be pretty obvious, why? It's because we visit last. So, if we were to simply move this up once, we'll do an in-order traversal, meaning, we go left, then we visit, then we go right.

[00:02:19]
So let's just see the difference in values when we do that. So we start here at 20, we go to the left, to 10, go to the left, 3, go to the left nothing, print out 3, all right, hey, same value to begin with. Go back up to the 10, print out the 10, go to the 15, left, right, 15.

[00:02:37]
Up to the 20, print out the 20. To the 25, to the 23, nothing on the left, print out the 23. Go to the right, nothing on the right, 25, print out the 25. To this side, left 27. Let me fix that 5, that's a terrible 5. Nothing here and back up the tree.

[00:03:00]
Notice what happened with our numbers. Our numbers are in-order. You wanna guess where they got the term in-order traversal from? If you have a binary search tree it produces in order, make sense? Yes, that should make sense because we know to the left is always less than. So we first go to the littlest node, visit that, and then start slowly going to the bigger side as we go.

[00:03:24]
So this should hopefully make sense, we're not gonna do pre-order traversal. I think you guys can guess what pre-order traversal does. We put the visit at the top, so we print out that first, so it'd go 20, 10, 3, 15, 25, 23, 27. And so, it just kind of goes that way, is that useful?

[00:03:40]
I don't know, I don't know any applications for pre-order traversal, I just know it exists. I've never had to use that yet. But, there you go, so this is binary search tree traversal. Do we have any questions for this?
>> Just kind of a general question, I can understand the concepts clearly, but when reading a question and trying to translate this actually into code.

[00:04:02]
Do you have any suggestions for how to do that?
>> Yeah, like how to translate this into code. First thing you gotta think of is how do you represent a note? There are several different ways depending on that, there are strategies. So the first thing I usually start off with, just simply the representation.

[00:04:16]
So, node of some sort of value t, right? We don't know what the value is inside of every single node, you're gonna have a left, that's gonna be potentially null, right? And it's also gonna be a node t, you're gonna have a right, exact same thing, it may not exist, node, right?

[00:04:34]
And then, you're gonna have a value, which is whatever the type is being held within there. So long as you see that, the rest should become more and more obvious. If you had to do a pre-order traversal, well, you just start with a node, you visit it, then you go to its left and call the same function.

[00:04:51]
It keeps on doing that, when it's done, you call right, you keep on doing that, and you're kind of done. And so, for me, representation usually is the first step to understanding a problem, as long as you know what shapes you're working with, the rest isn't too hard because now you're literally just going left, left.

[00:05:06]
Well, I'm walking left until there's nothing left to walk on. And so, it just becomes easy. So once you kind of make that jump, and it takes a few programming experiences to make that jump. Then implementing data structures become excessively easy as opposed to really, really hard. As you get to the more advanced ones like Prim's algorithm or Kruskal's, they just involve a lot more programing.

[00:05:26]
And then, all of a sudden, you also get a much wider choice of kind of the data structures you use in combination. So something to think about, fun times.
>> And what if the number three was the number 28?
>> What if the number 3 was 28? We would have a very lovely binary tree.

[00:05:48]
It just wouldn't be a binary search tree, cuz it has broken the fundamental rule of this should always be less than, cuz this is not less than its parent. So therefore, it's not a binary search tree, this is just a binary tree. Great times, everyone has two children, or one child, or no child, and filled with all the same types.

[00:06:05]
So, nothing unique about it, you couldn't use it for searching, it'd be kind of a worthless tree. I'm not even sure why you'd use just a binary tree at that point other than you're just displaying something in a document. Then you just become a general tree, which then you just become the DOM, right?

[00:06:17]
That's what the DOM is, it's just a tree with a bunch of children. Once you understand that, all of a sudden the DOM becomes a little bit easier. All right, no more questions for now. Well, we'll do more. Don't worry, we're gonna do more. Okay, we're looking pretty good.

[00:06:31]
So, I do wanna talk about, just in case we have to use these terms, I want you to make sure that you know them. So, this right here is obviously, we often call this the root. So this would be the root, it's just a node, it has no special designation.

[00:06:43]
I've been in classes where the teacher tries to make it such that the root is special, and so, therefore, you have a class that represents the root, and then a class that represents nodes. No, I mean every single, if you think about it, this is a root right here.

[00:06:57]
It is the root of a subtree, they're all all the same thing, that's just that. Typically, we call these things nodes. Typically people think of this as directed, meaning that you never traverse back up a tree. Even though that's not technically true, you don't typically traverse back up a tree.

[00:07:15]
All right, you let recursion do the recusing back up the tree. All right, now that we have that kind of figured out, the next thing is that, besides for the root, if we're looking at this person, this would be called the parent, the uncle, the children, these are siblings.

[00:07:32]
So that's usually what we say when we say all these phrases. And so, if I say, hey, a sibling, the left sibling, I'm meaning, this person's same level, same parent, child. And so, can you kind of get it because we all understand a family? So it kind of mostly makes sense, they describe it in familial terms.

[00:07:48]
All right, there we go, I think that's pretty much everything you will need to know to just excel and crush this course