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.