1 00:00:01,600 --> 00:00:02,260 Hi, everyone. 2 00:00:02,290 --> 00:00:06,250 So in this video, we are going to discuss the preorder, Trevor Salvatore. 3 00:00:06,490 --> 00:00:08,800 OK, so what exactly are the traversal? 4 00:00:09,070 --> 00:00:11,020 So suppose you have a root node. 5 00:00:13,260 --> 00:00:14,550 You have left Sabri. 6 00:00:15,770 --> 00:00:17,180 And you have right subtree. 7 00:00:19,120 --> 00:00:26,200 So preorder traversal CS, first you visit the data, then you go to left and then you go to right. 8 00:00:26,270 --> 00:00:27,560 OK, so what is the. 9 00:00:27,800 --> 00:00:29,590 So this is basically raw data. 10 00:00:29,650 --> 00:00:36,330 OK, so first visit the date of the root node, then visit the left subtree and then visit the right 11 00:00:36,340 --> 00:00:36,780 separately. 12 00:00:36,790 --> 00:00:38,230 OK, so data are left. 13 00:00:38,230 --> 00:00:38,560 Right. 14 00:00:40,090 --> 00:00:46,000 OK, data live right now, let's see this example and let us try to find out the broader traversal for 15 00:00:46,000 --> 00:00:46,490 distri. 16 00:00:46,540 --> 00:00:51,040 OK, so first of all, I'm standing here, so first data. 17 00:00:51,070 --> 00:00:56,210 So one will get printed first, then the left subtree and then the right SIPRI. 18 00:00:56,500 --> 00:00:58,650 OK, so what is the output for everybody? 19 00:00:58,730 --> 00:00:59,650 So first to. 20 00:01:00,690 --> 00:01:07,320 Then they left debris, so for then the right subtree fife, and finally this right subtree three. 21 00:01:07,400 --> 00:01:11,490 OK, so this is the period reversal for this by Nutri. 22 00:01:12,610 --> 00:01:15,250 Now, let us perform the trial set for distri. 23 00:01:15,280 --> 00:01:17,440 OK, so first data. 24 00:01:17,770 --> 00:01:23,290 So one, then the left subtree, so left three does not exist, then the right subtree. 25 00:01:23,320 --> 00:01:27,940 OK, now first two, then the left subtree, which is three. 26 00:01:28,150 --> 00:01:30,910 And then the right subtree, which does not exist. 27 00:01:30,940 --> 00:01:31,390 So it is. 28 00:01:32,470 --> 00:01:35,460 OK, so this is the traversal for this tree. 29 00:01:36,370 --> 00:01:37,510 OK, one, two, three. 30 00:01:38,850 --> 00:01:40,560 Now, let us consider this example. 31 00:01:41,310 --> 00:01:43,000 OK, so first her data. 32 00:01:43,350 --> 00:01:44,640 So that means 25. 33 00:01:46,370 --> 00:01:47,810 Then they left Sabri. 34 00:01:49,750 --> 00:01:57,190 And after left subtree, we have to go for it right subtree, so fallers are pretty a15 so 15 then they 35 00:01:57,190 --> 00:01:59,920 left subtree, so then. 36 00:02:01,020 --> 00:02:07,940 Then they live separately, so for then the right subtree, 12, OK, so 12, 15, then for 12. 37 00:02:09,199 --> 00:02:13,650 Then right subtree, so data left, right. 38 00:02:14,180 --> 00:02:19,580 So it will be 22, 18, 24, then 50. 39 00:02:22,000 --> 00:02:23,200 Then again, 35. 40 00:02:25,150 --> 00:02:30,310 So basically, Rita left and right, so 31 and 44. 41 00:02:32,060 --> 00:02:35,600 So data 70, left, right. 42 00:02:35,810 --> 00:02:37,940 So 66 and 90. 43 00:02:38,180 --> 00:02:41,450 OK, so period reversal is very simple. 44 00:02:41,480 --> 00:02:47,450 First you visit the data, then you visit the left subtree and then you visit the right subtree. 45 00:02:47,480 --> 00:02:50,070 OK, so there is data left, right. 46 00:02:50,300 --> 00:02:53,600 So we have to follow this order for each and every node industry. 47 00:02:53,660 --> 00:02:58,550 OK, we have to follow this order for each and every node of the tree. 48 00:02:59,150 --> 00:03:03,160 OK, so this is the period reversal for this by Nutri. 49 00:03:04,040 --> 00:03:06,060 Now, I hope you understood the question. 50 00:03:06,320 --> 00:03:09,690 So it's called will be very, very simple, but you have to do so. 51 00:03:09,700 --> 00:03:11,090 Suppose you have a function visit. 52 00:03:11,600 --> 00:03:15,210 So what this function will take as input, it will take root as input. 53 00:03:15,770 --> 00:03:16,990 So first of all, data. 54 00:03:17,270 --> 00:03:18,960 So I will print data. 55 00:03:19,010 --> 00:03:20,000 So route data. 56 00:03:21,720 --> 00:03:26,880 Then would I have to do I have to visit the left February, so I will call the function visit and it 57 00:03:26,880 --> 00:03:28,580 will visit the left subtree. 58 00:03:29,680 --> 00:03:31,900 And then I will visit the right subtree. 59 00:03:31,910 --> 00:03:35,970 OK, so I will call the function visit and I will give the right subtree. 60 00:03:37,720 --> 00:03:39,160 OK, very, very simple. 61 00:03:39,310 --> 00:03:41,590 This is data, this is left and this is right. 62 00:03:41,620 --> 00:03:42,490 So data left. 63 00:03:42,490 --> 00:03:42,820 Right. 64 00:03:44,440 --> 00:03:51,500 OK, so since so this is basically a recursive function, OK, the code is very simple. 65 00:03:51,820 --> 00:03:54,790 Now, let us write the code since you have understood the logic. 66 00:03:54,970 --> 00:03:55,330 OK. 67 00:03:56,250 --> 00:04:03,300 So this is the question I have to write the preorder, Trevor said, and the output for this mandatory. 68 00:04:04,370 --> 00:04:09,290 My output is one, two, three, OK, so I have to return vector of integers, I have to Rodenbeck profanity. 69 00:04:09,300 --> 00:04:16,700 Just so first, let us rate what is a simple what is a simple builder driver said, okay, so let's 70 00:04:16,700 --> 00:04:17,959 name dysfunction preordering. 71 00:04:19,430 --> 00:04:20,720 So it will simply take. 72 00:04:22,240 --> 00:04:27,250 No reason, but it will simply take root as input, not a simple case. 73 00:04:27,280 --> 00:04:32,230 So if Rudimental that mystery did not exist, so I can simply return. 74 00:04:33,840 --> 00:04:37,100 OK, I can simply return without printing anything now. 75 00:04:37,180 --> 00:04:39,580 We have to do I have to first print get data. 76 00:04:39,580 --> 00:04:40,140 Left, right. 77 00:04:43,030 --> 00:04:46,740 So data left, right, so this is data then left. 78 00:04:46,930 --> 00:04:49,030 OK, so I will call the function preorder. 79 00:04:50,600 --> 00:04:51,890 And I will pass left. 80 00:04:54,270 --> 00:04:55,290 So after I left. 81 00:04:56,700 --> 00:04:58,320 I have to visit the right subtree. 82 00:05:02,820 --> 00:05:06,660 OK, so I have to follow this order for each and every detail left, right. 83 00:05:09,600 --> 00:05:16,200 OK, so this is very simple code for people traversal, OK, first data, then left and then right. 84 00:05:16,470 --> 00:05:17,290 Data left, right. 85 00:05:17,330 --> 00:05:20,990 OK, now we will modified this code for our question. 86 00:05:21,000 --> 00:05:23,130 OK, so here we do not have to print anything. 87 00:05:23,490 --> 00:05:25,170 We have to return vector of integers. 88 00:05:25,680 --> 00:05:26,880 So let's create. 89 00:05:28,140 --> 00:05:31,890 Avedon said, OK, so let's call it let us call this transfer. 90 00:05:32,700 --> 00:05:34,500 Now I will call the function preorder. 91 00:05:35,610 --> 00:05:43,500 And I will give Root as input and obviously the answer and once I would answer it is ready, I can return 92 00:05:43,500 --> 00:05:43,930 my answer. 93 00:05:43,960 --> 00:05:47,350 OK, I've put a ton of integers, so I'm returning on set here. 94 00:05:48,120 --> 00:05:49,470 Now let us modify this code. 95 00:05:50,160 --> 00:05:56,210 So basically it will take a vector of integer says input and it will fill that vector. 96 00:05:56,220 --> 00:05:58,050 OK, so instead of printing. 97 00:06:00,060 --> 00:06:02,680 I will store the elements, OK? 98 00:06:02,730 --> 00:06:08,220 I have to store instead of printing, so Sadaat pushback value of fruit. 99 00:06:10,120 --> 00:06:14,320 OK, very simple and let us a bit this also so. 100 00:06:17,350 --> 00:06:19,180 Commands and commands. 101 00:06:20,200 --> 00:06:23,120 And one more thing, I have to pass this by reference. 102 00:06:23,140 --> 00:06:28,300 OK, I have to pass it by reference so that the changes are permanent, OK? 103 00:06:29,020 --> 00:06:32,010 Now, let's turn our code and then we will try to submit our code. 104 00:06:32,020 --> 00:06:35,270 OK, now let's submit. 105 00:06:41,680 --> 00:06:42,830 OK, so success. 106 00:06:42,850 --> 00:06:44,350 So our goal is working fine. 107 00:06:44,410 --> 00:06:44,750 OK. 108 00:06:45,100 --> 00:06:49,000 Now let us discuss the time and the space complexity for the preorder reversal. 109 00:06:49,750 --> 00:06:52,470 OK, so consider one example. 110 00:06:52,490 --> 00:06:56,050 So I have one, two and let's say three. 111 00:06:57,620 --> 00:07:03,890 And then let's say for so how the people travel survey work, so I will pass the road and I am passing 112 00:07:04,190 --> 00:07:04,770 the answer. 113 00:07:04,860 --> 00:07:11,200 OK, so initially my answer is somebody then answered or push back rude values or the system. 114 00:07:11,330 --> 00:07:12,650 So I will push one. 115 00:07:13,730 --> 00:07:18,710 Simple, then I'm calling on the left hand side, so left and side is basically nil. 116 00:07:20,220 --> 00:07:25,740 OK, so what is happening here is this is the call stack, so one is calling on the left hand side, 117 00:07:26,430 --> 00:07:27,900 left hand side is basically nil. 118 00:07:28,110 --> 00:07:29,670 OK, so if the route is null, return. 119 00:07:30,030 --> 00:07:31,800 So I will return to one. 120 00:07:32,780 --> 00:07:38,300 OK, then I'm calling on the right hand side, OK, root, right, so I'm calling on the right hand 121 00:07:38,300 --> 00:07:38,540 side. 122 00:07:38,570 --> 00:07:39,890 So when will call to. 123 00:07:40,840 --> 00:07:42,130 One is calling on two. 124 00:07:43,800 --> 00:07:50,790 Then what I will do, so I will push to inside, so we will get inside and then two will call on its 125 00:07:50,790 --> 00:07:54,940 left, so left does not exist for two, so two will call on. 126 00:07:56,130 --> 00:07:57,920 And if the route is well, I will return. 127 00:07:57,930 --> 00:07:59,970 So I will return back to to. 128 00:08:01,010 --> 00:08:03,020 Then will call on the right hand side. 129 00:08:03,180 --> 00:08:05,690 OK, so two will call on three. 130 00:08:07,840 --> 00:08:09,070 Then I will push three. 131 00:08:10,640 --> 00:08:15,260 Then three will call on left, which is for so trivial, calling for. 132 00:08:16,330 --> 00:08:23,530 Then Ford will call in it, so Ford will get inside, then four will call on the left subtree, which 133 00:08:23,530 --> 00:08:23,940 is Nele. 134 00:08:24,220 --> 00:08:30,150 So it will read, I will return to Ford, then Ford will return two, three, three will return to total 135 00:08:30,160 --> 00:08:32,110 return to total return, Duvan. 136 00:08:32,140 --> 00:08:34,240 And finally, of course, tech will become empty. 137 00:08:34,240 --> 00:08:35,190 And this is my answer. 138 00:08:35,200 --> 00:08:36,070 One, two, three, four. 139 00:08:36,100 --> 00:08:39,350 OK, you can see data then left and then right. 140 00:08:40,179 --> 00:08:43,030 So one data left separate does not exist. 141 00:08:43,030 --> 00:08:45,580 Then two data left separate does not exist. 142 00:08:45,850 --> 00:08:51,230 Then three data and then basically four and the right subtree for three did not exist. 143 00:08:51,250 --> 00:08:53,770 So this is how we will get our answer. 144 00:08:53,810 --> 00:09:00,460 OK, and we have to store, OK, we have to pass by reference so that the changes are permanent. 145 00:09:00,640 --> 00:09:06,400 OK, so that time complexity is basically big often because we have to go through each and every node. 146 00:09:06,820 --> 00:09:10,600 OK, and again, the space complexities big off and in the worst case. 147 00:09:10,800 --> 00:09:14,800 OK, so this is same as what in order driver said. 148 00:09:14,830 --> 00:09:16,960 OK, same as traversal. 149 00:09:18,960 --> 00:09:20,190 OK, thank you.