Depth First Tree Traversals

[00:00:00]
>> We are gonna do some tree traversals, I promise these are like a million times easier so you can kinda rest easy for a second. Again, that AVL tree is the most difficult thing that you're gonna learn in this course. So if you survived this far, you're over the crest of the mountain now, it's all downhill from here.

[00:00:23]
So let's talk about traversals. And these actually end up being kind of important just in general, with traversing graphs and traversing paths, and mazes, and trees, and all that kind of stuff. So let's talk about a tree traversal. So a tree traversal in this particular case, imagine I gave you this tree, I just handed it to you and said, I want an array of all the numbers in this array or in this tree.

[00:00:50]
How would you do that? There's a couple ways of doing it, and these are called traversals, right? So let's say I gave you this binary search tree, and I wanted everything. Just I don't care what order they come back in. Just give me all of the numbers that exist in the array.

[00:01:10]
You could do what's called a pre-order traversal, which is I'm gonna give you 8, 3, 1, 6, 4, 7, 10, 14, 13. So basically, just the order that you visit all the nodes in, right? So since I start on the root node, I'm going to give you 8 first, then I'm gonna go to the left child and I'm gonna give you 3.

[00:01:33]
Then I'm gonna the left child and I always go to the left first then right. Then I give you 6, then 4, then 7, then 10, then 14, then 13. So this is called depth first traversal because we're going as deep as we can first. And you can see here again using this tree up here, we call the method we'll call it pre-order traversal on the root node 8.

[00:01:58]
We add 8 to the array, then we call pre-order traverse on the left child 3, we add 3 to our array. We call pre-order traversal on the left child 1 just here, right? Maybe I can zoom out a bit so you can maybe see a little bit of what's going on.

[00:02:15]
So 1 has no children so you return up to here, and since we're doing this recursively, then we're going to process 6 next, right? And so on and so forth until you process everything in the array. That's called pre-order traversal, and you'll end up with this this array here 8, 3, 1, 6, 4, 7, 10, 14, 13.

[00:02:39]
If I'm asking you for just every number in the array, that's great, right? That's you successfully fulfilled everything that I'm looking for. Now, given this as a binary search tree, what if I wanted everything in numerical order? So I want 1, 3, 4, 6, 7, 8, 10,13, 14, how would you do that?

[00:03:06]
Well honestly, it's the same thing basically, we just changed when we add numbers to the array. So what we're gonna do is we're going to go as far left as we can. So I'm gonna do call post, or this is gonna be called in-order traversal. I'm gonna call in-order traversal on 8, then I'm gonna call in-order traversal on 3, I'm gonna call it in-order traversal on 1.

[00:03:30]
1 has no left child, so I add 1 to the array then I return. Then I add 3 to the array, and then I call in-order traversal on the right. So the only thing that's changing here is when I add the item to the array, right? Same exact logic go left, then go right.

[00:03:49]
But with pre-order traversal, it's add to the array, go left, go right. If it's in-order to reversal, it's go left, add to the array, go right. And then as you might imagine, there is a post-order traversal, which is go left, go right, add to the array. And just to demonstrate the difference.

[00:04:09]
Pre-order traversal gives you that number, in-order traversal gives you these numbers, and then post-order where I'm adding everything after I visit both the left and right child is this. So with post-order, always your route will just be last, right? Because that's the first thing that you call it with So, Why are we learning three different ways of doing the same thing?

[00:04:44]
It's a good question you might ask. If you want a sorted list out of an array, you're gonna use in-order traversal. If you wanted to make a deep copy of a tree, right? So if I gave you this tree and said, hey, I want a copy of this, how would you do that?

[00:05:02]
In this case, pre-order traversal is really helpful because you can create a new node and then add the children. So deep copies, you'd probably use a pre-order traversal. And then post-order would be great if you're trying to actually delete all the items in the array. Because what you'd wanna do is you want to visit both children, delete all of them, and then delete the node itself, and then return, right?

[00:05:24]
So post-order traversal would be something you'd probably do with a deletion.