One of the most important aspects of trees is how do we get the data out of a tree? How do we visit every single node and in what order do we visit these nodes? All of these topics is covered on this idea of a tree traversal. There's several different ways to look at a tree and several different ways to do a tree traversal. Let's take a look at a sample tree. Here's a tree that contains a total of nine nodes. These nine nodes are rooted at the plus node here at the root and then on left hand side we have minus, the right hand side we have times. We can see that if we view this tree in one way, we could possibly get a tree that has a math equation. Let's see how we might do this and let's look at different types of traversals. The very first form of a traversal is going to involve looking at every single node and then decide to go left, right or to shout that node out as we visit it. Let's see what happens if we go shouting out the node first, then go to left and then go to the right. So looking at this tree again, if we do shout first at every node, then travel left and then traveled right, here at the plus node, we're going to shout it out. The first thing we're going to say is plus. Awesome. Then, since we've shouted it out, we're going to go left. So here we're going to go to shout it out again. We shout out minus and then we're going to need to go left and right. So let's go left. Here at this node a, we're going to shout it out and we shout out a. Finally, we need go left. Left goes nowhere, then we come back to a. Then we need to right. Right also goes nowhere. So we're completely done with a, and now we can move back up to minus. We finished the left sub tree. Now we can go the right sub tree, here on the right sub tree. We're going to shout out division. Then we're going to go left. Going left, we get to b, we're going to shout out b. Then go to b's left which is nowhere, b's right which is nowhere. Now finally done with b we can return to the division. We've done shout, We've done left, we now need to go right. Shouting out c, left and right goes nowhere. We're done with c. Done with division, done with minus, back up to the plus the root node. Then we need to go to the right, going to the right, we now have the multiply sign, shout it out left, right. Left node goes to d, then right nodes goes to e. So the end of this process we've shouted out every single node within this tree. This is exactly what a traversal does. A traversal needs to visit every node in our tree exactly once and do something with that data. Here we did a traversal that's called a pre-order traversal. What we did is we shouted out our node first and then we went to left and then we went to the right. It's called pre because that's when we actually did the shouting out. That's when we did the visit of the node. If we think about the source code for this, that simply means we need to print out the value of our node. Then after we print out the value of our node then we do a recursive call to the left child and the right child. We go ahead and write this code real fast. Here in a binary tree member function. We're going to do a preorder traversal. The first thing we're going to do is we're going to call a shout function. That's going to happen on the current node. Then we need to call our preorder of cur left and our preorder of cur right. The final thing we need to do is we need to actually make sure we do a node check to ensure that we don't ever have a node pointer exception when we shout out cur or when we visit cur left, cur right, do that we simply add a null check around this entire function. If cur does not equal null, we run all of this code. Also we have a preorder traversal and I think you'll be able to find out exactly how an in-order and postorder traversal works. Let's go ahead and check them out. Just like before, we have a traversal and we've done preorder. Now, let's do inorder. In order means we are going to need to go left. Then we're going to shout it out. Then we're going to go right. So, line 52 has nothing, line 56 has nothing. Lines 54 does our shout out of our current node and we're doing an inorder traversal. So, we have the source code. Let's run the source code, inorder traversal means we do left shout right. So we've done left at the root node. So we move to left, left at the root node and move down here, left of a goes nowhere. So now we shout out a. The first thing we print out is a. Now we go back up, shout out the minus. Now we go into a right sub-tree. Go left sub tree. Here at b, we're going to shout out b because there's no left child. Then we go right, going back up to division. We shout it out division, then go right and go into c and we have a minus b division c. Going back up to the root we now have plus shouting out d times e. So all I did was do an inorder traversal of every single thing and look what we have. You have something that looks like a math equation. What we see is an inorder traversal in an ordered tree is going through the exact order things go into. So this tree happens to be a algebraic tree where we have a math equation encoded in the tree. If we add parentheses for layers then we can see that this code exactly shows us how we might go about encoding a math equation into a tree. The very last former traversal is a post-order traversal. A postorder traversal is the exact same logic except for we're going to shout at the end. We're going to do left, right, shout. That's going to be the exact order we visit every single node. What that means is the root node is going to be printed last because it's going to visit the entire left sub tree then entire right tree, sub-tree before shouting out the node. Let's do this real fast, just an example but it flows exactly the same way as before. Again, the order is going to be left, right, shout. This is going to be called a postorder traversal and visiting plus we go left. Left, we get to a we do left and right. Now, a, is shouted out. We then have visited left. We need to go right. Left, right here's b, we shout it out. Then c, we shout out division minus. Then we go to the right child, left child d, e times plus. This a postorder traversal of the exact same tree. So what you saw is we didn't vary the tree at all through this entire process. Instead, the only thing we did was change when we shouted out the node. Either at the beginning, before left and right, in the middle in an inorder or at the end, in a postorder. So these are the three most typical forms of a traversal that we see on a tree but there's one more that is completely different. So you may not want to actually go into left and right sub children. You may want a different form of traversal altogether. For that there is one special traversal that is widely used and that is a level order traversal. A level order traversal is going to read every single level, one level at a time. You're going to read the plus, the first level. Then the second level, then the third level, left to right. Let's see an example of that. So level order traversal is going to visit everything on the root level. Then everything on the second level. So we see plus on the root, minus times. Then everything on the third level, inorder a division d, e. Finally, everything on the last level b, c. This is a completely different way of visiting the exact same tree. Every single traversal we did had a unique ordering of things but every single traversal we did visit every single node exactly once. There's one last thing I want to mention in this video before we finish it up, which is the idea of a traversal in a search because often these terms are used interchangeably. Doing a traversal requires that every single node is visited. On the other hand, a search allows us to discover a particular node throughout the tree. So when we discover a node in the tree, we may not visit every single node. We may use a strategy developed into traversal to help us find a node quickly but a search ends as soon as we find that node while a traversal is going to visit up to every single node. This is a broad overview of what it means to do a search and what it means to do a traversal and different forms of doing traversals through out the tree which may influence the searches that we use later. We'll dive more into trees in the next video. I'll see you there.
