In this lecture, we'll look at a number of different ways that we can traverse a tree. Specifically, we'll look at three different kinds of depth-first traversal, we'll look at pre-order traversal, we'll look at in order traversal, and we'll look at post-order traversal and we'll also look at breadth-first traversal of a tree. This is the tree that we'll be traversing and I snagged this tree from the tree traversal page on Wikipedia so you can compare our results with those on the Wikipedia page if you'd like to do so. This is a binary tree, so each node can only have zero, one or two children. To support this lecture, I implemented binary tree node and binary tree classes so if you download the lecture code for this lecture you can see how that works. We regularly talk about left child and right child for each node, we don't have a list of children we just have a left child and a right child. Okay, let's go see how these traversal techniques work. In the main method of our lecture code, the first thing we do is we call a method that I wrote to build the tree that I showed you a picture of. And then we're going to demonstrate the pre-order traversal by calling the pre-order traversal method and then we'll do an in-order traversal, a post-ordered traversal, and then will do a breadth-first traversal as well. So let's take a look at the pre-order traversal, the pre-order traversal method is pretty straightforward. First, we checked to make sure the node that was passed in and I'm calling this perimeter tree because it really is a tree that is rooted at that node. So we make sure the node that was passed in isn't know that will be our indication that we should stop recursing, we process the node first and by process here I just mean we write the value of the node and then if the left child isn't know we recursively call this method with the left child and then if the right child isn't know we recursively call the method with the right child. So this is using recursion to do a traversal of the tree and the pre-order part of the traversal means that we do the node then we do the left child, then we do the right child. So for the graph that are traversing you can see that node F is marked as one so we process node F, then we recursively call the method on the left child. So here we are at Node B and we process that node and we recursively call the method on the left child so we get to A and we process that and then we return from this recursion and now we call the method on the right child. So we do D and then we recursively call on the left child. So we have C on the right child so we have E and then we back up all the way through these recursion back up to our root and that was just processing the left sub-tree. So now we process the right sub-tree. So we first get to G and we process G and G doesn't have a left child. This is actually a right child of G so we will immediately process the right child and that's I we process the node and then we go to the left child. When I run the code, if you look at the output of the node values in the pre-order traversal that is exactly what I said it would be as we walked our way through the picture. So a pre-order traversal means we do the node then we do the left side, then we do the right side, and we do that recursively. For an in-order traversal, we traverse the left child first, then we process the node, then we traverse the right child. So we don't do the node at the beginning here we do the node between the left child and the right child. For the graph where processing, as you can see, we go as far down on the left as we can. So we process A first and then we do B the node, then we work our way down the right side, but once we get to D remember we do left first so C is next and then the node and then the right side, and then we come all the way back up. So we already did all this stuff on the left so we now process F and we do the same thing on the right hand side. Running the code again if you look at the in-order traversal output. That's what I just said. And by the way, these are now in alphabetical order, from A to I, and for the last depth first traversal technique will look at post order traversal and the difference here is we do the left side, then we do the right side, then we do the node. So again we go as far down as we can on the left side, so we do A and then we move up through B to D and go down on the left side. So we do C next then we come up to D and back down and do the right side. And then finally we do D and now we've done the left and the right side of B. So we come process B backup the root. Now we're going do the right side before we process the root. So we come down here and we can still do the right side before we process G and we can still do the left side before we process I so left side of I and back up here and I doesn't have a right child. So now we just process I and back up to G and we've done the non-existent left child into the existing right child. So now we can process G and now because we did the left side of the tree and the right side of the tree we can finally process the root. And this time, you should look at the post-order traversal output and see that that is the order that I said that this would be in. And those are the three depth first traversal techniques and you should recognize them as depth first because we were working our way as deeply down the tree as we could before we were doing things. We do have a breadth-first traversal technique as well, where we'll process the root, and then we'll process everything one step away from the root, and then we'll process everything two steps away from the root, and so on. I implemented the breadth-first traversal method using the technique that we used before when we were searching a graph. So I have a search list here, I don't need a path, I'm just going to process each node so this is a little more simple than looking for a path through the graph but I am using a search list and I'm adding to the end of it, and I'm adding to the end of it because I'm doing breadth-first search and I'm just gonna process that search list and each time I'll pull the first thing off the front of the search list and I'll process it and if there is a left child, I'll add it at the end of the search list and if there's a right child, I'll add it and the end of the search list. And remember, this was the difference between depth first and breadth-first search. In depth first search, if we're using a search list we add to the front of the list but because we're doing breadth-first search here I'm adding new nodes to the back of the list instead. So this picture should not surprise you, we process F first, then we process B and G, those nodes that are one step away from F, then we process A, D, and I, the nodes that are two steps away from F and then finally, we process C, E, and H. And as you can see, for the output for the breadth-first traversal that is exactly the order that I said it would be in. To recap, in this lecture, we saw a number of different ways to traverse a binary tree and we also saw numerous examples of recursion in the depth first traversals that we implemented.
