All right, I want to finish off with binary trees and binary search trees with some tree traversals in particular, pre order in order post order and level order. You see these tree traversals come up now and again, so they're good to know. I want to focus on pre order in order and post order to begin with because they're very similar. They're also naturally defined recursively and you can sort of get a feel for why they have their certain names that they do. So pre order prints before the two recursive calls. In order will print between recursive calls and post order will print after the recursive calls.

So if you look at the three functions on the left, the only thing that's different between them is where the print statement is. So let's go on to some detail on how pre order works. So on the right, I'm going to maintain a call stack of what gets called. So when we're recursing back up, we know what called us to know what node to go to. And what you need to know about pre order is that we print the value of the current node and then we traverse the left subtree followed by the right subtree. So for order, what we're going to do is gonna start a, print A, and then we go left, your B, and we go down to D, go down to each.

And now we recurse back up, so we push node h off the call stack and go to D and then we go to AI and then Then we explore i. Now we're at the bottom, so we recurse back up, so we push it off the call stack. We've already processed D and go back to B we also already process B, but now we have to do bees. right subtree so we own explore E. And we've explored ease. So push frame off the stack explored B, push that off the stack. And now a, now we need to explore the right subtree of a.

So we would print C, then f, then j, and then the bottom so recurse and then lo K, no bottom. So recursive push node k off the stack. Note f off the stack. And now explore node C's, right subtree. So, g now l. And now we're done. We curse all the way back up, and we would exit our function.

And at the bottom, you can see what the preorder traversal is. Okay, now let's cover inorder traversal. So how inorder traversal works is we traverse the left subtree. Then we print the value. And then we traverse the right subtree. And for this example, I'm going to be using a binary search tree and not just a generic binary tree, and you'll see something interesting happens.

We push no 11 on the stack because it's our route and we go left, then we go left again and go left again. And notice as I was doing left, I would push those on to the stack. But I'm not printing the value yet, because when I call in order, the very first instruction in the in order is to go left. I only print once I've traversed the entire left subtree. If I'm a leaf node, like I am now one is a leaf node, then I've already explored the left subtree, if you will, so I can print the current value, then I recurse. And then I print three because I've explored threes left subtree now we go right now.

And I've explored both subtree so I can print five recurse and print six because I've explored sixes left subtree I can go to eight and recurse and print 11. Now I need to finish elevens right subtree. So go, right, go left, go left, I have explored 12 recurs and we're going to print 13. Then go down to 14, print 14. Also because 14 has no sub trees go up. So push 14 out of the stack, push 13 out the stack, print 15 because we will export fifteens left subtree go Right.

Right. And now, the last thing we need to do is finish our function by just pushing everything off the stack. So cool back up. And now did you know something interesting happened when we did our in order traversal. Well, what happened was we printed the values of the nodes in increasing order, which is why it's called an inorder traversal. If you do it on a binary search tree, it prints the values in increasing order, which is really neat.

That's a quite a nice property of the inorder traversal. Now, let's look at the post order traversal. And post order traversal says, okay, traverse the left subtree then traverse the right subtree. And after you're done doing both of those, only then print the value of the node. So this means if you look at our tree right now, the last value we're going to print shouldn't be 11. Because we need to process elevens entire left subtree elevens entire right subtree So let's start at 11 and explore its left subtree.

So got me down, then print one because we've explored both its left and right subtree. And don't print three because we haven't explored the right subtree yet. Print five because we've explored both sub trees which don't exist. Now we can print three because we've explored both of its sub trees. And then similarly, they go down to eight, print eight recurse and print six. Don't print 11 because we still need to do it's right subtree go 15 1312.

Print 12 for 13, print 14, go back up to 13. Now we can print it don't print 15 yet, because we haven't explored all of its right subtree and your 1719 and then Pop everything off the stack and print on the way back up. And you can see that laughing is indeed the last node we have visited. And that's pre order in order and post order nutshell. Now I want to look at level order traversal, which is special, it's quite a bit different from the other two. A level order traversal is we want to print the nodes one layer at a time.

So start with 11. They want to print six and 15 and three 813 17 and one 512 14 and 98. Like, oh, how am I going to do that? And the way we're going to obtain this ordering is by doing something called a breadth first search from the root node all the way down to the leaf node search now what a breadth first search is from graph theory. This the same thing, a tree is a type of graph, it's no different. So what we're going to do to do our breadth first search is we're going to meeting the queue of the nodes we have left to explore.

And how that's going to work is our queue is originally going to contain only the root node. And we're going to keep processing by pulling out the first value in our queue until our queue is over. A bit more detail on that. So here, you can see the queue. On the right, I've inserted node 11. And so I would pull out number 11.

And I would add elevens, left child and right child to the queue. So they would go at the end of the queue. And I've also removed 11. So, so the next notes process would be six followed by 15. And then I will keep adding children to the queue so that I reach them eventually. So let's have a look.

So I've pulled 11 from the queue, and now added six and 15 to the queue. Now the next thing on the top of the queue is six, so it removes six and add six children three and eight to the queue, then fifteens. Next up, add 15 children which are 13 and 17, to the queue, and next up in the queue is three. So I would add threes, children to the queue, and then move on, explore eight, eight has no children, so I can't add them. Next 13. And you can see that as I'm exploring nodes, I just add the children By keep pulling the most recent thing in the queue, and this gives us the level order traversal that we want.

And this is how you do a breadth first search in general. So not too complicated, except we had to use that special trick of using a queue instead of using a stack. So we don't do level order traversals recursively, we need to do them iteratively with a queue. And that's it for binary search trees and tree traversals. We're going to be looking at some source code in the next video. And that should be really interesting.

So stay tuned for that. Or if you just want look at the source code, I put a link in the description below for my GitHub repository. So definitely check that out lots of great data structures there. And that's all for this video. I'll catch you next time.