Tree Traversals

[00:00:00]
>> So we're gonna talk about traversals and we're gonna kind of constrain this down to a binary tree. So traversals are your most basic operation you can do on a tree a traversals where you attempt to visit every single node. All right so let's just do that now.

[00:00:15]
This is where it gets really fun, this is also where hopefully your knowledge of recursion is pretty good because at this point we're gonna be doing a lot of recursion. So, I'm just gonna write up a tree. There's gonna be no ordering to it, I'm just gonna be putting in random numbers that I see fit.

[00:00:30]
I don't know why I'm choosing the numbers, they all felt right up looks like that one's going to 7. All right, there we go. This one's now officially 7. And practically speaking, a lot of trees will also have a parent reference. So they can go both ways, especially if you're doing rotations and other things.

[00:00:54]
I didn't really talk about the parent reference, but it is something that you consider. So a traversal is as simple as this. Is that you're gonna do something called visiting a node. Which means you're gonna do something with the value of the node. And then we're going to recurse.

[00:01:12]
Recurse, of course, is that fun operation of calling a function to do the same thing again, but on a new node. And so that means we're gonna need to have a good base case. We're gonna have a pre or a post and recurse step. And so there's 3 types of tree traversals.

[00:01:27]
And it really just depends on where you do the visiting of a node. And let me kind of show you what I mean by this. So let's just say that we're right here we start off with the root of the tree. If I were to do a traversal, in which I just simply print out the value of each node that I find It would look a little something like this.

[00:01:44]
So if I visited node, and then I simply recursed. Starting at this node, it would look a little something like this. I would print out a 7, and then I would recurse left. I would print out a 23. And then I'd recurse left. Then I'd print out a 5 and then there's nothing left to recurse, right?

[00:02:03]
Those are that's a terminus node right there. I pop back up to 23. And then I traverse right, I print out the node, nothing left to recurse. Go back up, nothing left to recurse. At this point, go up to 7, go down to the right hand side. 3 go down to recurse down to the left hand side print out an 18.

[00:02:20]
Then no children left, go back up to 3, go to the right-hand side, print out a 21. And there we go, we just visited all the nodes and we did it in a specific ordering. We visited the node then we were cursed. This type of traversal is referred to as a pre order traversal.

[00:02:37]
I first visited the node, then I did the recursion pre order, right? That makes a lot of sense. There's actually 2 other type of orderings. So I'm gonna rename this from recurse to recurse left, and then I'm gonna have recurse right? This changes the order in which we visit the nodes.

[00:02:59]
In this case, of course, we're just printing. So that means we're gonna go to 7, we then recurse left as you can see right here. We go to 23, then we recurse left. We go to 5, nothing to recurse on the left-hand side, we print the node. We go to the right-hand side, nothing to recurse.

[00:03:17]
We pop back up, we print 23. Then we go down to the right hand side nothing to recurse on the left we print 4 then we go back up it's done we go back up to 7 we then print 7 and then we recurse down the right hand side.

[00:03:31]
If we go to 3, we recurse down the left hand side, there's nothing to go any further left. So therefore we print 18. Come back up, we print 3 and go down the right hand side, nothing left to recurse 21. So hopefully this kind of is an interesting way to do this.

[00:03:45]
Now we've kind of switched up the order in which revisiting notes and this will actually make a difference in certain types of sorting with the binary search tree, if I'm not mistaken in order traversal will actually print out in order to array. So there is reasons why you want to use these things specifically.

[00:04:01]
There's one more traversal we will do which is called a post order traversal. So we covered pre order, in order, post orders we simply visit the node. But after doing the recursion, we have a question.
>> What is the difference between strong and weak ordering?
>> So, we will get to a thing that is weak ordered.

[00:04:21]
So a heap will have something like this, where this node is saved the minimum node. Then after that everything below it is larger than it. That's considered a weak ordering and that holds true throughout the whole tree. That means this node is the minimum at this point and everything below low it is larger.

[00:04:41]
In other words it's not strictly ordered it's not like 12345 it could be 1, 5, 2 right it could be out of order but it's still in an order that is weak.
>> Is this traversal expensive?
>> Well let's go over that after this so, let's just finish this last traversal alright.

[00:05:02]
So if we did visit node here at the end, it would obviously produce a different ordering to how we visit this and this can become really we're not gonna do an example of this today. But if we are using language in which you need to clean up memory, doing a post order traversal, where you free the memory is how you have to do that because you first have to get to all the children, and then on your way out you have to delete back up.

[00:05:25]
So there is reasons why you'd use different orderings. And so, let's just do a post order. So post order, you visit 7, awesome. But you don't, or you go to 7 but you don't visit it yet. You go left, you go left, now you're at 5 right here.

[00:05:39]
You try to go left, you try to go right, you come back out. So 5 is the first one on the post order. Then you have hopped back up to 23 and you go right you can either go left or right at 4. So therefore 4 is next then 23 and then we're all the way back up at 7.

[00:05:54]
Now we go down to the right hand side we go down to the left hand side and now a 18 we can either go left or right, so we have 18. We pop back up, we cannot visit 3 quite yet we go down on the right hand side 21.

[00:06:06]
Then we pop back up 3, then we pop back up 7. So the root note is notice it's at the end this time preorder roots at the beginning. In order roots in the middle post order routes at the end do you see how that works hopefully you see how that works.

[00:06:22]
And if you don't see how that work we are gonna program this. But what is the running time of this? So this is where you're going to have to put on your head and think of what is our input I keep talking about that remember rule one. Running time is always the growth with respect to the input.

[00:06:38]
So what would be the input in this case? The whole tree that is right that's perfect which means that we have to visit every single node in the tree. So if our tree doubles in size, how many more operations do we have to do? Double, exactly. So what type of growth is that?

[00:06:59]
>> O of N?
>> Boom, O of N, linear, right? It grows linear with it. It does not grow quadraticaly. A good way to do that. And you can always tell if things grow quadratically or linearly. If you double the input, does it quadruple the amount of work or does it double the amount of work?

[00:07:14]
If it quadruples, the amount of work you're doing area, if it eight folds the amount of work you're doing volume, you can kinda see how that works. Volume of course, is n cubed. So yes, so all traversals are n. This makes inherent sense, right? If there's n nodes, you have to visit all n nodes.

[00:07:30]
It's effectively a 4 loop if a for loop existed in this case which it does but I'm going to show you that later. All right so there we go we just got done doing the three traversals that are kind of like the most basic traversal of a tree or the the way to do it awesome pre order in order and all that.

[00:07:46]
So we're going to code all these. And they it's really quick and easy to code up.
>> And that last tree can each branch only have each node have only two branches or can be more than that.
>> So that was a binary tree. So notice that we're at it I mean, in order post order or pre order traversalIng does not matter how many children you have, right.

[00:08:13]
So you can think of it like if you're walking the DOM and you want to print out the entire tree of what the DOM looks like say to the standard out you would do some sort of traversal where you visited it. Doesn't matter how many children it has I only did it as a binary format because it's very easy to understand, I go left, I go right.

[00:08:32]
Now an in order printing of a general tree, obviously very confusing. At which point is at the middle node, right? You can't really have a middle node in a general tree but you can do a preorder and a post order very simply. You print out the value of the node before you visit all the children or you visit all the children and then print out the value of the node.

[00:08:51]
And obviously visiting the node depends on what you're doing. In this case, we're simply printing it. So if you really think about this, whoopsies, everything we're doing right now is effectively just a linked list, especially binary trees. They're just a linked list. Where the next and previous is just a little bit different, right?

[00:09:07]
We have left and right. They don't point back to each other. Each one has two branches instead of one branch. So it's not like a huge amount has changed from yesterday. It's just slightly more complicated and in some sense, the programming also can get very, very much more complicated, but we won't do any of that complicated.