1 00:00:00,450 --> 00:00:05,250 ‫So now we're going to write our code for depth first search post order. 2 00:00:05,820 --> 00:00:10,470 ‫So I'm going to bring up a tree and then we'll start our code off like this. 3 00:00:10,770 --> 00:00:15,210 ‫And what I'm going to do here is bring in the preorder code. 4 00:00:15,240 --> 00:00:19,620 ‫This will be exactly the way we had this in preorder. 5 00:00:19,890 --> 00:00:21,040 ‫In preorder. 6 00:00:21,060 --> 00:00:22,800 ‫We output the value. 7 00:00:23,280 --> 00:00:27,120 ‫And then we went left and then we went right. 8 00:00:27,420 --> 00:00:31,550 ‫So with post order, we're going to have all this same code. 9 00:00:31,560 --> 00:00:34,080 ‫It's just going to be in a different order. 10 00:00:34,320 --> 00:00:39,000 ‫We're going to take that sea out statement and move it to the bottom. 11 00:00:39,270 --> 00:00:45,270 ‫And that is the only change we need to make to turn order and to post order. 12 00:00:45,720 --> 00:00:50,550 ‫And just like we did with preorder, we're going to overload the function. 13 00:00:50,550 --> 00:00:54,540 ‫So this is going to be the version that we call in the main function. 14 00:00:54,840 --> 00:00:59,850 ‫So for now, I'm going to remove that last line and bring in a call stack. 15 00:01:00,210 --> 00:01:06,630 ‫So we're going to start off by calling this on the route that will be that 47 node. 16 00:01:06,900 --> 00:01:10,370 ‫But we're not going to print out the value yet. 17 00:01:10,380 --> 00:01:18,480 ‫First, we're going to go left to the 21 node and add an instance with the 21 node, and then the 21 18 00:01:18,480 --> 00:01:19,980 ‫node is going to go left. 19 00:01:19,980 --> 00:01:26,700 ‫And we'll add an instance with the 18 node, and then the 18 node is going to look left, but there 20 00:01:26,700 --> 00:01:30,210 ‫isn't an item there, so that it's going to look right. 21 00:01:30,210 --> 00:01:36,270 ‫And then finally, that instance that was called on the 18 node will come down to this line and we'll 22 00:01:36,270 --> 00:01:38,490 ‫print out that value. 23 00:01:38,670 --> 00:01:43,410 ‫So now that instance is done running and it will be popped from the call stack. 24 00:01:43,710 --> 00:01:48,420 ‫So now the instance that was called on the 21 node is the active instance. 25 00:01:48,420 --> 00:01:49,470 ‫It has gone left. 26 00:01:49,470 --> 00:01:51,570 ‫Now, it will go right. 27 00:01:51,900 --> 00:01:54,990 ‫So we'll add an instance with the 27 node. 28 00:01:55,230 --> 00:01:57,600 ‫The 27 node is going to look left. 29 00:01:57,600 --> 00:01:59,280 ‫It's going to look right. 30 00:01:59,610 --> 00:02:03,600 ‫And then finally it's going to print out its value like this. 31 00:02:03,930 --> 00:02:07,740 ‫And now that's done running and it will be popped from the call stack. 32 00:02:08,070 --> 00:02:11,610 ‫So now the instance on the 21 node is active. 33 00:02:11,610 --> 00:02:13,710 ‫It has gone left, it has gone right. 34 00:02:13,710 --> 00:02:18,270 ‫And now we'll print out the value from that node like this. 35 00:02:18,570 --> 00:02:23,040 ‫So now that instance is done running and it will be popped from the call stack. 36 00:02:23,370 --> 00:02:27,600 ‫So now the instance that was called on the route is the active instance. 37 00:02:27,840 --> 00:02:30,960 ‫It has gone left now it will go right. 38 00:02:31,200 --> 00:02:34,530 ‫So now we'll call an instance on the 76 node. 39 00:02:34,890 --> 00:02:39,000 ‫It is going to go left and call an instance on the 52 node. 40 00:02:39,330 --> 00:02:46,230 ‫That instance is going to look left and then look right, and then finally print out the value of 52. 41 00:02:46,710 --> 00:02:49,590 ‫And now that will be popped from the call stack. 42 00:02:49,920 --> 00:02:54,750 ‫So now the instance called on the 76 node is active, it has gone left. 43 00:02:54,750 --> 00:02:58,980 ‫Now it will go right and add an instance with the 82 node. 44 00:02:59,250 --> 00:03:05,190 ‫The 82 node is going to look left, it will look right, and then finally print out its value. 45 00:03:05,610 --> 00:03:08,460 ‫And now that will be popped from the call stack. 46 00:03:08,760 --> 00:03:15,330 ‫So now the instance that was called on the 76 node is active again and has gone left and right now it 47 00:03:15,330 --> 00:03:20,040 ‫can print out its value and it will be popped from the call stack. 48 00:03:20,340 --> 00:03:23,850 ‫And then finally the instance called on the 47 node. 49 00:03:23,850 --> 00:03:31,890 ‫It has gone left and right now we can print out that value of 47 and now that will be popped from the 50 00:03:31,890 --> 00:03:32,730 ‫call stack. 51 00:03:33,400 --> 00:03:37,990 ‫And that will be our output for depth first search post order. 52 00:03:38,530 --> 00:03:44,380 ‫So we'll look at this code in a moment in vs code along with this line as well. 53 00:03:44,530 --> 00:03:52,240 ‫And when we do, we'll create this tree and then we'll run depth first search post order on that tree 54 00:03:52,240 --> 00:03:54,790 ‫and we'll expect this output. 55 00:03:55,180 --> 00:03:58,420 ‫So now let's flip over and take a look at this. 56 00:03:59,510 --> 00:04:04,280 ‫So this is the depth first search post order function that we just created. 57 00:04:04,280 --> 00:04:07,220 ‫And once again, this will be overloaded. 58 00:04:09,530 --> 00:04:16,220 ‫And then in our main function, this creates that binary search tree and this adds all of the nodes 59 00:04:16,220 --> 00:04:18,500 ‫to make it look like it did in the diagram. 60 00:04:18,650 --> 00:04:23,180 ‫And then with this line, we'll run depth first search post order. 61 00:04:23,510 --> 00:04:29,480 ‫So I'll run this and that returns the values and the order that we expected. 62 00:04:30,240 --> 00:04:36,390 ‫And that is our member function for depth first search post order.