Implement Tree Traversal

[00:00:00]
>> Here we go, so let's go back to our kata machine that we installed yesterday. If you're not familiar with the kata machine, you can go get it right here. It's at my GitHub/kata-machine, the README is a bit risque as I mentioned yesterday, here we go. So we're gonna jump back in, and we're gonna go to whatever day you've generated.

[00:00:15]
I think I generated a few extra in here, and we're gonna go through these three files. BT, binary tree, InOrder, PostOrder, and PreOrder. So we'll just start with PreOrder cuz I think that's the easiest and what we're given is the head to the tree. Usually we call this the head or the root, I tend to call the head and what I want to return out are the visited nodes in that order.

[00:00:38]
So we're gonna do a pre order array of our tree, so how are we gonna do that? Well, in general, what I tend to do is always create a second function whenever I'm doing recursion, right? So let's do a function walk that takes in just a node, it doesn't have to be a specific note, all right?

[00:00:53]
We owe binary we're not gonna just simply assume that this is the head, let's see, what are we doing? It's a number IRJI already have it as a number, awesome. And then I'm also gonna have our path, which is a number array and then I can also return it back out just to make it super convenient.

[00:01:08]
Awesome, and so one more thing remember, when we're doing recursion, we have to consider our base case. What is the base case of a traversal?
>> I mean, you've seen something or not or if you?
>> Nope, so if you're seen something or not, no because a traversal luckily uses the stack to keep ordering for us.

[00:01:35]
The function call stack to keep ordering for us, so the traversal really or the base case if you really think about it is when we are at a node that doesn't exist. We've gone to a child that's not actually there, so the best case where we stop recursing is right here, that is the spot.

[00:01:52]
Please, we can no longer keep going down, we are done recursing, we can say, hey, we will stop here at this moment. So let's go here and go if not current then return path, there we go cuz we're just making it convenient. Even though we're passing in path we're also returning path and it just makes it super convenient for down here cuz then I can just go work turn a walk head array.

[00:02:15]
Super convenient with either, you don't have to do that but I just find it convenient. There we go so, that's the base case we've gotten to the point in which we do not wish to keep recursing or we cannot actually recurse any longer. So now remember I also told you yesterday that in recursion Aug actually comes with three sub steps and the three sub steps of the recursive step is.

[00:02:39]
Pre, recurse, post and I did that intentionally because I wanted today to be easier, because now we're doing a pre and in order and a post. So you can imagine where each of these operations go. So since we're in a pre walk, we will first push into our path the node value, right.

[00:02:59]
So path push, current, value, we're doing this as the first step in our recursion here, and just to make it clear I'll put it right there. And then now we need to recurse, so we need to visit the left hand side and then the right hand side. Typically when you're doing traversals of a tree especially a binary tree, you always traverse left than right, why?

[00:03:20]
Maybe a binary search tree influenced this, I don't know, you don't have to technically, it would just be weird if I saw something that didn't do it, right? It's like one of those conventions where yeah, in a linked list you can call it next and previous or you can just call it A and B.

[00:03:31]
It doesn't really matter what you call it but it would just be weird to do it differently. All right, so let's just do that for niceness and now let's recurse, so I'm gonna recall walk with curr.left and curr.right. There we go and then of course, don't forget to put in the actual path oopsies.

[00:03:51]
There we go, we got the path in there and now it's a null, I forgot I did that. That's how silly of me to do that, there we go, so now we have null as the other value. So if we hit a node in which it doesn't exist, it will just simply return else we keep on recusing until we get to the bottom.

[00:04:11]
There we go, now post, do we do anything in post? No, we've already visited the node by pushing into the path, then we walk, we're done. So the last thing I need to do is just return out the path, right? There we go, so as we recurse, we will keep walking, keep walking, keep walking, hit a dead node.

[00:04:28]
Or hit an empty node, go back up the stack add the node to the value, go down the other way if it's empty, come back up and I'll just keep on going. So hopefully this all makes sense, is there any questions right here cuz I feel like this is a very fundamental part of tree traversal.

[00:04:43]
And we'd much rather answer any questions right now than have it be ignored because we're only gonna be doing tree traversals for quite some time coming up.
>> What does returning path and base case do?
>> So the reason why return path and base case and right here is that effectively a it's my signature right I have it right here.

[00:05:01]
But it's really just a convenience here, what I'm gonna do is I'm going like this I'm gonna put this as void. And I'm just gonna simply return and then I don't need to put anything right here, right? We don't need to return, well that means right here I need to change this signature.

[00:05:16]
So I'm gonna go like this const path equals an array then I'll have to pass in path so it gets mutated as it walks and then return back out path. It's really just a convenience more than anything else, so there is no reason why you have to do that, other than if, I say my return signature is a number array.

[00:05:36]
Then I have to return that path no matter what, even if it is a base case and it actually doesn't really leave the recursion. And so you just consistency compilers is the answer, we got one more question.
>> From someone who doesn't know type script, what's a number is it in an int?

[00:05:53]
>> All right, so a number is a beautiful value in which is either a floating point number, or I think it's a floating point nearish 64 bits or it can be an integer up to 2 to the 53 minus 1. It's pretty standard operation really in any language is 2 to the 53 minus 1 we've all been there, who hasn't been there before, right?

[00:06:17]
Which actually is a huge pain in the butt because we'll say WebSocket algorithm if you get a 127 in the second byte you have to do a 64 bit read of a number. In which JavaScript can't do that, so you have to do like a big in read of a number, very, very annoying, it's just terrible.

[00:06:38]
Anyways sorry, keep going.
>> Do you need to set path from the return value of the walk which is called in walk?
>> Do I need to set the what? One more time.
>> Do you need to set path from the return value of the walk which is called in walk?

[00:06:57]
>> I don't need to set, I mean the only thing okay, so, I think I understand the question, the question, I believe I'm gonna try to restate it. Do I need to mutate path in any way or do I need to mutate or hold on to the value that's returned from walk?

[00:07:12]
I actually am not quite sure what it's asking but I'll try to explain it the best I can what we're doing with this path. So the path is an array in JavaScript everything that you pass and is passed and effectively by pointer unless if it's a number. And so at that point, if I mutate whatever is passed in, it will actually happen to the value that was containing it, right?

[00:07:31]
This is not an immutable item, this is not C++ where if you pass in a vector, it actually copies it unless if you pass it by reference, just think of it as passed in by reference always. And so when I pass this in, as I walk I mutate the thing that was passed in.

[00:07:45]
And so I mutate it, then I pass it into the next walk function, I mutate that pass into the next walk function. So everything will be added in order of wherever I put this in. If it's pre in or post, and then afterwards, I just simply have to return it because it's been mutated by the walk function.

[00:08:07]
Does that make sense? Yeah.
>> Base case should return path, no?
>> Well, I took that out, remember to show that I don't actually need to return the number it was just simply a convenience. So I don't have to do this little song and dance right here where I create the item, pass it in or turn it out.

[00:08:27]
Instead, I can just do this by simply returning it right here return path, I'm not creating anything, right? Cuz when I return path I'm just returning a reference to it, right I'm just simply returning a reference to something that was already created, it just was created right here.

[00:08:47]
So I don't have to create that handle to it within my function. I just like it better, it's not like it's anything fantastic. All right, I think we're good to go, so what I'm gonna do is I'm gonna take all this, and I'm gonna copy all of it.

[00:09:04]
Just to make this a lot easier, we're gonna copy all of it and then we're gonna open up BTInOrder. All right, so I'm gonna paste all of it, go all the way down, move my walk into my new function and then erase the pre order one. And now we have the exact same function inside here we have pretty much the exact same setup and I'm gonna move this.

[00:09:25]
I need to do something with this, right cuz this is where we visited the node, correct? All right, so what do I need to do with this in an in-order traversal? If you don't remember, this is an in-order traversal is this one right here. We need to go down our left hand side until we can no longer go left, then we visit the node, then we go down our right hand side.

[00:09:48]
And then that eventually bubbles all the way back up, so what is the change we need to make to this code? Right now we are visiting the node, then going left, then going right. In in order, we go left, visit the node, go right So We just put it In bitwixe, the two walks, right we split that walk in twain It is fantastic, right?

[00:10:13]
So now we walk left until we can no longer walk left, we push an R value or visit the node. Then we walk right and let the whole algorithm redo itself, make sense? It's just I mean, it's just literally that simple, right? So again, let's just copy the whole thing and let's open up post order and again I'm gonna paste it all in.

[00:10:35]
Go down here, move this into the post order function just so it's like named beautifully, you don't even need to do that cuz it's a default export. Default exports don't actually consider name, so we could have done it any way you want to, again what do we do here?

[00:10:47]
In a post order world, we go left, then we go right, then we visit the node. So how should this code change? Well, yeah, that's right born on Friday, we do that we push it down, we move it down one, and bam, we got it. So there we go, that is a post order traversal, it's really not that hard.

[00:11:10]
In fact, I can push it down to right here to kind of show you hey it's in the post section of it all. And that's it, that is a post, a pre and in order traversal and just to prove that I'm not lying to you cuz I can just hear right now people really like why are you saying?

[00:11:26]
MPX gest I believe if I only do order this might get all three I don't know how many tests we're gonna get. Yes we got them all, done look at that we got all three of them first try that's a triple threat first try. So I get compared to the doctor sometimes, anyways that's a pretty inside baseball joke right there I'm sorry about that.

[00:11:47]
All right so there we go we just got done doing traversals, all three types of traversals and they're all fairly easy right that was only a couple lines of code. All right, so these types of traversals are known as depth first, why are they known as depth first?

[00:12:03]
Let's jump back here and kind of explain why that is, when you do recursion obviously you keep calling a function with itself, right? And you keep on passing in something new until you get to a base case. Which means if we do an in order traversal we are going to go left all the way until we can no longer go left.

[00:12:20]
In other words we're gonna go as deep as possible in this tree on the left hand side and then visit a node. Then we're gonna go right once and then go as left as deep as possible and then come back and visit that node. And so if you think about we always go depth first, right that's what that means, that's why it's called the DFS or depth first search or depth first traversal.

[00:12:46]
So there we go but now there's actually another type of traversal which is a breadth first. But before I do that I wanna ask something, what implicit data structure did we use during a depth first search?
>> Binary node or binary tree.
>> That's the data structure we definitely used but doing the traversal we used an implicit data structure.

[00:13:10]
Something in which we didn't specify but it's actually being used. Let me write it out, I bet you this will make more sense once I read it,, I wanted to do this because I really want to strongly tie. All these data structures together this is from yesterday, so right now my top note is 7,23,5.

[00:13:27]
So I'm just gonna kind of write out in in order traversal, all right, so if you think about it, we first start off at 5, right? Wait was it 7 or 5 I've already forgot okay, 7 at the top, pretend they wrote 7 their first drive. All right so we start out at 7 and then we visit what is it?

[00:13:45]
20 something, my goodness how have I forgot this in my head it's 23, 23 awesome 23. And then we visit 5, right and then we print out the value at 5, then we try to go right and we can't go right. So we pop it off then we're at 23 and we try to go right which of course we can go right and so a 4 gets put on.

[00:14:12]
We can no longer go, we cannot do any more traversal and we printed out and that gets popped off, then we can no longer do any more traversing at 23, so that gets popped off. What data structure is that? Boom stack that's just a stack we're implicitly using how we call functions as a stack.

[00:14:33]
Does that make sense? I think it really doesn't it and really helps you visualize I think recursion a bit better to realize you're just pushing and popping on a stack. That's all you're doing which means we can technically do any of these traversals without using recursion. We just simply have to add the children to a stack and we do the same thing, pretty neat I think it's pretty neat.