Depth First Tree Traversals Practice

[00:00:00]
>> So you're gonna go over here to code sandbox. This is in tree traversals. We're gonna do the depth first traversals first here. You have three methods here that I need you to code up. And they're all extremely similar in terms of what code, they are doing. My code here just to make sure each one of these I have taking, 1,2,4,5 lines of code.

[00:00:35]
Each one of these is five lines of code. They're essentially the same code just slightly in different orders. Okay, you have a tree here. Each one has a value a left child and a right child. The right child might be null and the left child might be null.

[00:00:57]
And these are the numbers that you expect to get out of them. So there's gonna be recursive methods. And again, they're all gonna look really similar. You're just actually gonna shift one line for each one of these. So you're gonna say, first thing base case if no node, return array, and I am going to, make this not auto refresh, there we go.

[00:01:26]
We're gonna say array.push node dot value. Then array equals pre-order traverse. Node dot left array. Array equals pre order traverse node dot right, array, return alright So. This is it for preorder traverse. So basically saying, if I have no node, so if I call this like a empty node or a null node, then do nothing, just return the array.

[00:02:27]
I push in the value. And then I call the pre order traversal on the left node, and I call the pre order traverse on the right node. And then at the end of this, I just return the array. So the other two in order as you might imagine.

[00:02:47]
So first of all, let's. Change those to be in order traverse so they're calling a correct method. As you might imagine, I just move when I do the push. That's it, that's the whole thing. One more time post-order traverse this one's really gonna shock you of how it works.

[00:03:12]
So we're gonna copy and paste this, paste that so that's postorder traverse. And what you do here is you just move it down one line, that was it not as it's not gonna shock you at all. Or maybe we'll I don't know he might be easily surprised. That's it, that's all the traversing that's we're gonna do here.

[00:03:33]
Let's make sure that my code works here. We're gonna run our tests again and here in traverses. Traversals our, I need to change the skip down here. Run this again, Then traversals depth first reversals solved.
>> And can we do a quick like pseudocode step through of like just one of them.

[00:04:04]
Just to kind of get, visual light, you have a three node tree, just something quick, to see how that works.
>> All right, here's our three node tree that I just invented now. In a pre-order traversal. The first thing you gonna do, is gonna cut on the root note, right?

[00:04:31]
Cuz that's all you have, right? Is the root note of the tree. You're gonna have your array, right, that you're trying to get all of the numbers gathered up into. In a pre-order traversal the first thing you're gonna do is add 8 to the array, right? Pre, we're gonna add it to the array first, then you call it on the left node.

[00:04:49]
So you call preorder traversal on the left node. Again, first thing you need to do here is call, you're gonna add three. So now we have eight comma three. We'll call on the left node. That's no.we'll call it on the right node, that's no, and then this returns right, so returns back to eight here.

[00:05:07]
We're then going to call pre order traversal. On 10, right, that's gonna attend to the array. It's gonna call on the left node on the right node, those are both nodes. So we end up with eight 3, 10.In order traversal,again, you would do it with, you're gonna call it, in order traversal on 3.

[00:05:35]
You're gonna call it on its left no, which is no. Then you're gonna add three to the array, then we're gonna call it on the right node, nothing there. So we have three, this returns up here. This is now totally processed that it's left sub-tree, so we're gonna add eight to the array.

[00:05:49]
So we're gonna have three comma eight, and then we're gonna add the right or we're gonna call in order traversal on the right node. So we're going to call it on its left child. No, we're gonna add 10 to the array, so we're gonna have three 8, 10.

[00:06:02]
Then we're going to go into call it on its right node, nothing there. Okay, one more time. We're gonna do it with post order traversal. Here, we're gonna call Postal retroversal on 8. We're then gonna call it on 3, three is gonna call it on its left child, then its right child.

[00:06:21]
Both of those are no it's gonna return back, so then we're gonna add 3 to the array, right? This is gonna return up here. Then we're gonna call postal retroversal on 10. We're gonna call it down here. It has no left child, has no right child. Then we're gonna add ten to the array.

[00:06:36]
It's going to return up here and then finally, on the root node, we will add eight to the array, right? So, then we end up with three, 10 eight in post order traversal.