1 00:00:01,070 --> 00:00:01,730 Hi, everyone. 2 00:00:01,760 --> 00:00:05,300 So in this video, let us discuss what is posted at traversal. 3 00:00:06,540 --> 00:00:14,430 OK, so suppose you have this root node, then you have the left subtree and you have the right subtree. 4 00:00:15,210 --> 00:00:21,300 So Bulstrode Traversal says first you visit the left subtree, then you visit that I had subtree and 5 00:00:21,300 --> 00:00:23,580 then you visit the data of the root node. 6 00:00:23,610 --> 00:00:26,850 OK, so NRD left subtree right. 7 00:00:27,240 --> 00:00:29,400 And the date of the root node, very simple. 8 00:00:29,430 --> 00:00:33,510 OK, now let us apply the poster trevisan on this by Nutri. 9 00:00:33,720 --> 00:00:41,880 OK, so first left, this will be number one and then the right separates or two and number three, 10 00:00:41,910 --> 00:00:42,870 which is the data. 11 00:00:43,120 --> 00:00:46,650 OK, so it will be basically left subtree. 12 00:00:48,390 --> 00:00:51,690 Right subtree and so so five to. 13 00:00:53,110 --> 00:00:55,060 OK, so when is completed? 14 00:00:55,090 --> 00:00:56,140 Now let's go for two. 15 00:00:56,170 --> 00:01:00,120 So this is only three, so likely three and two is visited. 16 00:01:00,220 --> 00:01:02,440 So let's go to number three one. 17 00:01:02,620 --> 00:01:06,640 OK, so this is the Beausoleil traversal for Destry. 18 00:01:07,840 --> 00:01:13,690 Now, let us discuss the post-war traversal for Destry, very simple left right data, so left does 19 00:01:13,690 --> 00:01:14,290 not exist. 20 00:01:14,710 --> 00:01:20,700 Now let's go to right, OK, so left three right does not exist data. 21 00:01:20,890 --> 00:01:22,020 So left right data. 22 00:01:22,060 --> 00:01:22,840 So three, two. 23 00:01:22,840 --> 00:01:23,510 And then one. 24 00:01:24,640 --> 00:01:27,300 So this is the poster traversal for distri. 25 00:01:28,300 --> 00:01:30,940 Now let us write the poster traversal for distri. 26 00:01:30,940 --> 00:01:32,820 OK, I remember left right data. 27 00:01:33,550 --> 00:01:39,100 OK, so left right data for 2010. 28 00:01:40,750 --> 00:01:49,060 Simple again, left right data, so this will be 18, 24, 22, then 15. 29 00:01:51,270 --> 00:01:54,840 So left is completed now let's go for the ride. 30 00:01:54,840 --> 00:02:06,990 Sabry so left right data So this will be 31, 44 and 35 again left right data to this will be 66, 90 31 00:02:07,710 --> 00:02:08,610 and 70. 32 00:02:09,120 --> 00:02:09,900 Then 50. 33 00:02:10,639 --> 00:02:11,760 OK, so 50. 34 00:02:12,790 --> 00:02:17,380 Now, the rights are pretty complicated, so left is completely dry, discomfited now data. 35 00:02:17,410 --> 00:02:20,330 OK, so left, right and data. 36 00:02:20,350 --> 00:02:21,420 So now 25. 37 00:02:22,360 --> 00:02:26,140 OK, so this is the poster traversal for this by Nutri. 38 00:02:27,490 --> 00:02:28,960 So I hope you understood the logic. 39 00:02:29,140 --> 00:02:30,070 Let us ride the cold. 40 00:02:30,100 --> 00:02:31,530 So cold will be very, very simple. 41 00:02:32,170 --> 00:02:33,790 So let's say you have a function visit. 42 00:02:34,070 --> 00:02:38,730 So this visit function will take root as input and what it will do. 43 00:02:39,010 --> 00:02:40,560 So first of all, left subtree. 44 00:02:40,570 --> 00:02:47,640 So I will visit the left subtree, then I will visit the right subtree, left right data. 45 00:02:48,430 --> 00:02:50,090 So let us visit the right separate. 46 00:02:50,170 --> 00:02:54,970 And then finally I can directly, I can print, I can visit the data. 47 00:02:55,150 --> 00:02:57,100 OK, so very simple. 48 00:02:58,280 --> 00:02:59,980 Left right data. 49 00:03:00,020 --> 00:03:00,920 So this is left. 50 00:03:01,190 --> 00:03:05,060 This is right and this is data, OK, very, very simple. 51 00:03:05,090 --> 00:03:06,290 Now, let us write the gold. 52 00:03:07,740 --> 00:03:13,470 OK, so again, if this is Nedry, this is the poster traversal three to one. 53 00:03:13,770 --> 00:03:16,140 OK, now let's write the code. 54 00:03:16,140 --> 00:03:21,720 So first we will write the simple code for post water and then we will modify the code according to 55 00:03:21,720 --> 00:03:22,290 the question. 56 00:03:22,330 --> 00:03:22,650 OK. 57 00:03:27,950 --> 00:03:29,440 So first of all, the base case. 58 00:03:29,450 --> 00:03:33,470 So if rotational, that means the crew did not exist. 59 00:03:33,470 --> 00:03:34,800 So you can basically done. 60 00:03:34,890 --> 00:03:35,230 OK. 61 00:03:37,170 --> 00:03:42,060 Then I have to follow the order left right data, so both order. 62 00:03:45,500 --> 00:03:45,950 Left. 63 00:03:47,590 --> 00:03:48,370 Dendrite. 64 00:03:59,870 --> 00:04:01,510 So left, right, and then later. 65 00:04:07,450 --> 00:04:08,780 OK, so very, very simple. 66 00:04:08,800 --> 00:04:13,900 So this is the code for BORSTAR Driesell, first left, then right and then later. 67 00:04:14,280 --> 00:04:18,620 OK, so in this question I have to return the property just so there's no need to print. 68 00:04:19,000 --> 00:04:20,260 So again, I will create. 69 00:04:21,420 --> 00:04:27,340 A vector of integers, let's say the name of the vector is answer, I will call it the function Bulstrode. 70 00:04:29,610 --> 00:04:34,710 I will give the road Nordhausen, but I will give them three years in port and I will give the answer 71 00:04:34,710 --> 00:04:38,190 Victor and finally I will return my answer. 72 00:04:38,640 --> 00:04:46,950 OK, now let us modify the function so it will take a vector of integers as input and obviously by reference, 73 00:04:47,460 --> 00:04:48,840 the name of the vector is answer. 74 00:04:48,880 --> 00:04:54,660 OK, so instead of and here I have to modify so I will pass answer. 75 00:04:56,310 --> 00:05:02,070 And answer, and instead of printing the value, I will store it in the onset of that. 76 00:05:02,130 --> 00:05:03,210 OK, Sir Lancelot. 77 00:05:04,340 --> 00:05:04,910 Bushwack. 78 00:05:07,040 --> 00:05:07,490 Well, you. 79 00:05:09,050 --> 00:05:11,510 OK, so let's run and then we will submit. 80 00:05:16,180 --> 00:05:17,350 OK, now let's meet. 81 00:05:22,040 --> 00:05:27,050 OK, so level code is working fine now let us discuss the timing, the space complexity for the postal 82 00:05:27,060 --> 00:05:27,470 address. 83 00:05:27,990 --> 00:05:34,790 OK, so again, that time complexity is basically big often as we have to visit each and every node 84 00:05:34,940 --> 00:05:37,820 and the space complexity in the worst cases big often. 85 00:05:37,850 --> 00:05:40,880 OK, so this is complexity is due to the collision course. 86 00:05:41,180 --> 00:05:42,320 So it is due to the collision. 87 00:05:42,980 --> 00:05:43,370 OK. 88 00:05:44,600 --> 00:05:49,010 And is the number of nodes, total number of nodes presently by Nutri? 89 00:05:49,070 --> 00:05:53,150 OK, now let us compare all the traversal. 90 00:05:53,450 --> 00:05:56,840 OK, so, you know, traversal traversal and Beausoleil traversal. 91 00:05:57,380 --> 00:06:00,280 OK, so what is in order traversal. 92 00:06:01,250 --> 00:06:05,840 So in order to wss first you visit left then data and then right. 93 00:06:05,870 --> 00:06:09,740 OK, so left-to-right what is preorder traversal. 94 00:06:10,310 --> 00:06:15,110 So Purita is first you visit data, then you go for left and then you go for. 95 00:06:15,260 --> 00:06:15,460 Right. 96 00:06:15,740 --> 00:06:19,190 OK, so basically if you see carefully this is top down approach. 97 00:06:21,320 --> 00:06:23,120 We are visiting from top to down. 98 00:06:23,180 --> 00:06:24,500 OK, so if you have a tree. 99 00:06:25,540 --> 00:06:28,480 You have you have you have left and then you have right. 100 00:06:28,510 --> 00:06:31,910 So what I am doing first data and then left and then right. 101 00:06:31,930 --> 00:06:33,760 So basically this top down approach. 102 00:06:33,970 --> 00:06:35,970 OK, I'm going from top to bottom. 103 00:06:36,700 --> 00:06:38,920 Now, the third one, which is the poster that. 104 00:06:42,040 --> 00:06:46,090 So this is first who is it left, then who was it right and then who is it? 105 00:06:46,090 --> 00:06:46,570 Data. 106 00:06:46,670 --> 00:06:50,170 OK, so if you see carefully, this is bottom up approach. 107 00:06:51,790 --> 00:06:53,110 This is bottom up. 108 00:06:53,180 --> 00:07:01,390 OK, you have RWD, you have the left subtree, you have the right subtree and what you are doing left 109 00:07:01,390 --> 00:07:02,230 right data. 110 00:07:02,250 --> 00:07:07,870 So first I will visit the left, then I will visit the right, and then I will move ahead, move up 111 00:07:07,870 --> 00:07:09,190 and then I will visit route. 112 00:07:09,240 --> 00:07:10,960 OK, so this is bottom up. 113 00:07:11,860 --> 00:07:13,630 So I'm repeating myself in order. 114 00:07:13,630 --> 00:07:14,410 It is very simple. 115 00:07:14,680 --> 00:07:18,130 You visit the left, then data and then right subtree. 116 00:07:18,160 --> 00:07:21,310 OK, so Eliade preorder is very simple again. 117 00:07:21,880 --> 00:07:22,690 Data left. 118 00:07:22,690 --> 00:07:23,120 Right. 119 00:07:23,170 --> 00:07:30,350 This is top down approach because first I am visiting the top node and then I'm going down ok. 120 00:07:30,400 --> 00:07:35,170 I am going down and I'm printing the left and the right post today is different. 121 00:07:35,470 --> 00:07:38,250 So Postgres left right data. 122 00:07:38,530 --> 00:07:39,670 So this is Bottom-Up. 123 00:07:39,730 --> 00:07:45,100 Why this is a Bottom-Up because first you are visiting the left subtree, then you are visiting the 124 00:07:45,100 --> 00:07:47,250 right subtree and then you are visiting up. 125 00:07:47,680 --> 00:07:49,420 OK, so very simple. 126 00:07:49,420 --> 00:07:50,770 This is a top down approach. 127 00:07:50,770 --> 00:07:54,070 This is bottom up approach and this is simple. 128 00:07:54,220 --> 00:07:55,190 Left, right. 129 00:07:55,520 --> 00:08:02,850 OK, and the time and space complexity for all the three approaches is basically big often and big often. 130 00:08:02,890 --> 00:08:08,350 OK, so this is team, you know, traversal traversal and boaster traversal. 131 00:08:08,710 --> 00:08:12,460 OK, so these are two different types of traversal that we can perform. 132 00:08:14,130 --> 00:08:15,900 OK, thank you.