Binary Search Tree Traversals

all right I want to finish off with binary trees and binary search trees with some treat reversals in particular pre-order in-order post order and level order you see these treat reversals come up now and again so they're good to know I all 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 lets you want 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 our order what we're going to do is insert a print a and then we go left your B and we go down to D go down to H and now we recurse back up so we push node H off the call stack and go to D and then we go to I and then we explore I now we're at the bottom so we recurse back up so we push I off the call stack we've already processed the and go back to be also are a process B but now we have to do bees right subtree so we go and explore e now we've explored be so push frame off the stack explore be push that off the stack and now a now we need to explore the right subtree of a so we would print see then F then J and then read the bottom so recurse and then that K and out bottom so weaker so push note k off the stack push node ass off the stack and now explore node sees 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 pre order traversal is ok now let's cover inorder traversal so how in order traversal works is we traverse the left subtree that 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 to binary tree and you'll see something interesting happens we push nodes 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 going 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 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 Mary curse now I can print six because I've explored sixes left subtree and you can go to eight and recurs then print 11 now I need to finish 11th or right subtree so go right go left go left now explore 12 recurse and we're going to print 13 then go down to 14 point 14 also because 48 has no sub trees go up so push 14 out the stack push 13 out the stack print 15 because we will explode 15th left subtree go right go right and now the last thing we need to do is finish our function by just pushing everything off the stack so let's go back up and now did you notice something interesting happened when we did our inorder traversal well what happened was we printed the values of the nodes in increasing order which is why it's called an in order 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 nice property of the inorder traversal now let's look at the post order traversal and post order traversal says ok traverse the left subtree then traverse the right subtree 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 should be 11 because we need to process 11s entire left subtree and let it an entire right subtree so let's start at 11 and explore its left subtree so gold me down then print one because we've explored both its left and right subtree now don't print three because we haven't explored its right subtree yet print five because we've explored both the sub trees which don't exist now we can print to be because we've explored both of its sub trees and then similarly go down to eight print aid recurse and print six don't print 11 because we still need to do its right subtree because 15 13 12 print12 go to 13 print 14 go back up to 13 and now we can print it don't print 15 yet because we haven't explored all of its right subtree and you're 17 19 and then pop everything off the stack and print on the way back up and you can see that Levin is indeed the last node we have visited and that's the pre-order in-order and post order a nutshell now I want to look at level order traversal which is a special is quite a bit different from the other to a level order traversal is we want to print the nodes one layer at a time so start with 11 they want to print 6 and 15 and 3 8 13 17 and 15 12 14 and 19 any 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 so if you know what I breath research is from graph theory and this the same thing that a tree is a type of grass it's no different so what we're going to do to do our breadth first search is we're going to maintain a queue of the nodes we have left to explore and how is going to work is our cue is originally going to contain only the root node and we're going to keep processing I 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 insert a node 11 and so I would pull out note 11 and i would add Elevens left child and let the right child to the queue so they would go at the end of the queue and and I've also removed 11 so so the next node process would be 6 followed by 15 and then I would keep adding children to the queue so that I reach them eventually so let's have a look so I pulled 11 from the queue and now added 6 and 15 to the queue now the next thing on the top of the queue is 6 so it removes 6 and add 6 is children 3 and 8 to queue then 15 is next up and I would add 15 children which are 13 and 17 to the queue and next up in the cuse three so i would add three children to the queue and then move on explore 88 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 but 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 if using it q instead of using a stack so we don't do level ordered traversals recursively we need to do them iteratively with a Q and that's it for binary search trees and treat reversals 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 to look at the source code I put a link in the description below for my github repositories definitely check that out lots of great data structures there and that's all for this video I'll catch you next time