WEBVTT 00:02.320 --> 00:07.700 Hi in this episode we will learn what is a binary tree and why are they so useful. 00:08.080 --> 00:15.460 Then we will learn how to implement one and also during this implementation we will cover a very powerful 00:15.580 --> 00:18.700 programming concept which is recursive functions. 00:18.730 --> 00:26.410 So far all of our examples has been using media data structures which means that elements on the data 00:26.410 --> 00:29.320 structures are sequential like this. 00:29.470 --> 00:33.730 So we have 10 8 20 9 0 15 and 25. 00:34.450 --> 00:41.770 All of these items or elements are on the same level binary trees are part of what it's called Tree 00:41.770 --> 00:42.940 structures. 00:42.940 --> 00:50.960 So rather than having a single level items we have a hierarchy like this. 00:51.020 --> 00:57.930 So compared to the previews like literally the structures are tree has different hierarchies. 00:57.950 --> 01:04.070 So in this case eight is US Chamber of 10 as well as 20 and so on. 01:04.330 --> 01:11.030 So a binary tree is a tree where every node passed and most to Children's. 01:11.090 --> 01:14.090 So how do we build a binary tree. 01:14.090 --> 01:18.480 Let's say we want to convert the linear destructor into a binary tree. 01:18.650 --> 01:24.730 So we start with the root node which is 10 and then we have to up the node number 8. 01:24.860 --> 01:29.450 So we will compare estate less or equal than 10. 01:29.990 --> 01:33.180 If it's lower than 10 we will add these to the left. 01:33.180 --> 01:35.930 No otherwise we will add this to the right note. 01:37.740 --> 01:40.300 So A is lower than 10. 01:40.380 --> 01:43.590 We will have this item to the left side now 20. 01:43.590 --> 01:47.040 What happened with 20 20 is bigger than 10. 01:47.520 --> 01:50.360 So all of these to the right note. 01:50.700 --> 01:58.410 Now here comes a special case will happen with 9 so we start on the road again and we will compare 9 01:58.680 --> 02:01.180 with 10 is 9 lower than 10. 02:01.190 --> 02:10.030 Yes someone wanted to go to the next node which is good child node often is 9 lower than 8. 02:10.030 --> 02:10.930 No. 02:10.930 --> 02:16.640 So we will at this to the right side and so on. 02:16.700 --> 02:20.730 So the same for 0 will go through 10. 02:20.880 --> 02:23.630 It's slow when we go to the left we go. 02:23.630 --> 02:32.390 We compare with 8 is slower we go to the left 15 is bigger than 10 but it's lower than 20 and 25 is 02:32.390 --> 02:34.840 bigger than 10 and bigger than 25. 02:35.240 --> 02:40.250 So why are binary trees useful basically for searching. 02:40.250 --> 02:48.480 So if we have a dataset like this but instead of having seven items we have millions of items. 02:48.740 --> 02:56.930 If we want to look for the item twenty five on a linear destructor we should check for every item in 02:56.930 --> 03:01.530 this case he's twenty five people at that no he's twenty five. 03:01.580 --> 03:10.040 He was to wait no until we find it so we will have to do seven operations which means that the bigger 03:10.330 --> 03:14.690 the size of the set the harder to find it. 03:14.870 --> 03:23.710 In contrast in the binary tree what we do is rather than traversing the whole tree we go and we said 03:24.220 --> 03:28.220 is twenty five bigger or lower than ten. 03:28.260 --> 03:35.350 What is bigger to the right now the moment we go to the right. 03:35.520 --> 03:40.360 We don't have to check any of those items because we know they are smaller than twenty five. 03:40.710 --> 03:42.950 So we split the set in half. 03:43.080 --> 03:48.450 Now we'll just have three left items to traverse. 03:48.480 --> 03:50.840 We compared twenty five with twenty. 03:51.000 --> 03:52.620 We know we have to go to the right. 03:53.220 --> 03:56.790 So we don't have to check any of those on the left side. 03:57.210 --> 04:00.750 And finally we find it now on the smaller samples. 04:00.750 --> 04:04.760 Doesn't make too much sense or you probably won't be able to see the difference. 04:04.780 --> 04:12.480 Then when you have massive datasets like databases they use these sort of algorithms to make it very 04:12.480 --> 04:13.500 more performance. 04:14.010 --> 04:17.360 So let's get started with our implementation. 04:17.430 --> 04:21.860 The first thing I wanted to do is defined tree structure. 04:22.030 --> 04:26.310 So let's say tree and the tree will contain a node. 04:26.760 --> 04:27.380 OK. 04:27.410 --> 04:28.540 Now what is a.. 04:29.360 --> 04:33.440 I know it's a ghost truck which contains a volume. 04:33.660 --> 04:40.240 Let's use it as we've been doing and then we said that a binary tree has either left or right. 04:40.290 --> 04:41.340 Children. 04:41.340 --> 04:44.650 So let's do left will just hold on. 04:45.360 --> 04:45.850 Right. 04:45.960 --> 04:46.950 Which is a node as well. 04:46.970 --> 04:47.700 Okay. 04:47.760 --> 04:50.160 And let's define a main function. 04:50.200 --> 04:50.470 Okay. 04:50.940 --> 04:52.070 So far so good. 04:52.140 --> 05:04.080 The first operation we will introduce is is our right for adding values and these will receive value 05:04.080 --> 05:04.740 of pi. 05:04.770 --> 05:08.850 It is interesting it will return our tree. 05:08.910 --> 05:09.990 Then you will see why. 05:10.290 --> 05:13.690 So far let's just return ourselves. 05:13.890 --> 05:14.280 Right. 05:14.970 --> 05:15.340 Okay. 05:15.510 --> 05:17.040 So how does this works. 05:17.040 --> 05:25.200 First we will verify that the node of this tree is not empty or kneel and if it's empty which will be 05:25.200 --> 05:34.910 the first gate where we need to align our tree we will do the node equals to know the value value. 05:35.130 --> 05:35.430 Right. 05:35.430 --> 05:38.860 So we're creating a node otherwise we will do to. 05:38.910 --> 05:39.870 No. 05:39.910 --> 05:41.400 Is there value. 05:41.750 --> 05:42.060 Okay. 05:42.600 --> 05:44.460 And then we return ourselves. 05:44.460 --> 05:50.820 So now we're calling the insert from the node which means that node needs to implement an insert function. 05:50.820 --> 05:51.120 Right. 05:51.180 --> 05:53.460 So that's the same. 05:53.790 --> 05:54.110 Okay. 05:54.420 --> 05:57.570 So what we're doing here is the following. 05:57.690 --> 06:04.950 First as we just saw in value is lower equal than the current value. 06:05.130 --> 06:07.530 We're going to the left right. 06:07.580 --> 06:09.880 Otherwise we're going to the right. 06:09.890 --> 06:10.200 Okay. 06:10.440 --> 06:12.450 So let's assume we're going to the left. 06:12.560 --> 06:12.980 Wait. 06:13.040 --> 06:19.730 2 verified cases that the node doesn't exist which means no Neil. 06:19.860 --> 06:22.990 Isn't that like the example when we are the number 8. 06:23.070 --> 06:23.760 Right. 06:23.820 --> 06:28.170 We went to verify 10 and the left side is nil. 06:28.170 --> 06:33.390 So we will create a new node on the example that will be 8 with value. 06:33.890 --> 06:34.510 OK. 06:34.890 --> 06:38.740 Now let's say there was a value on this on the left side. 06:39.150 --> 06:44.400 All new and the left insert the value. 06:44.400 --> 06:45.980 So what's happening here. 06:46.020 --> 06:47.750 I told you in the introduction. 06:47.970 --> 06:56.010 This is what's called recursion which means that node defines an answer function and inside that function. 06:56.190 --> 07:00.590 I'm calling the same function the now my node points to a different note. 07:00.960 --> 07:01.370 Okay. 07:01.620 --> 07:08.910 So for the right place is pretty much the same which means that E and the right doesn't exist. 07:08.940 --> 07:11.250 We will create a new node 07:14.050 --> 07:19.480 all the Y and the right user recursion again value. 07:19.920 --> 07:20.340 Okay. 07:20.470 --> 07:24.810 So let's revisit this function again. 07:24.840 --> 07:32.550 This is the first operation we compare the values a binary trees has a child which says that is the 07:32.550 --> 07:40.680 value is smaller than a specific one we go to the left which is this case the other child. 07:40.860 --> 07:45.400 Sorry if the value is bigger or else we go to the right. 07:45.400 --> 07:45.610 Right. 07:45.890 --> 07:48.390 So we have these two children. 07:48.390 --> 07:54.000 So now we should be able if everything is fine to create a tree. 07:54.080 --> 08:01.830 We'll use this notation and then we will insert some values the same on the example so insert pen and 08:01.890 --> 08:08.850 then we should do to the user eight twenty nine and so on. 08:09.180 --> 08:18.490 But if you remember insert is returning the same tree so all we could do like a shortcut here and ask 08:18.660 --> 08:27.990 insert is returning the same tree we could change these methods which is the use for 10 dot E's or 8 08:28.180 --> 08:31.090 but instead planning and so on. 08:31.510 --> 08:37.240 So this is really handy where you want to do many operations of the same type you want to change those 08:37.240 --> 08:45.910 methods and also go through boards to do multi line chaining which is you can up every method call in 08:45.910 --> 09:00.060 a different line so it reads pretty nice and easy so let's insert number nine member 0 15 and finally 09:00.230 --> 09:00.920 twenty. 09:01.130 --> 09:01.550 OK. 09:01.710 --> 09:07.050 So let's run this and make sure everything is going well. 09:07.050 --> 09:07.540 Yeah. 09:07.740 --> 09:13.090 Nothing happens because we're not bringing anything but at least he's not breaking anything. 09:13.110 --> 09:13.390 OK. 09:13.620 --> 09:21.270 So let's try to bring this let's define a function call brains know which receives as an argument. 09:21.750 --> 09:25.860 I know and doesn't return anything. 09:25.860 --> 09:29.550 So the first case we might have empty nodes right. 09:29.670 --> 09:34.140 Which are like the children's of the last node by the way. 09:34.140 --> 09:36.710 The last nodes on a tree are called Leeds. 09:36.750 --> 09:38.690 So the first thing I wanted to check is that. 09:38.710 --> 09:40.590 No it's not empty. 09:40.690 --> 09:42.710 You can something we just return. 09:42.720 --> 09:45.310 And now little bit more about recursion. 09:45.450 --> 09:54.140 We will first bring the value of know and then we will print it its Childs so how do we print an on 09:54.560 --> 09:55.470 again print. 09:55.550 --> 09:59.800 Note the left side means no the right side. 09:59.990 --> 10:06.810 OK so again Perino we'll take an old argument probably the first note on the parent note or the root. 10:06.810 --> 10:10.150 Now we know that the group No 10. 10:10.160 --> 10:13.160 In the example we just saw has two children. 10:13.520 --> 10:19.090 So we will print the left one and the right one and we're going to use the same function. 10:19.100 --> 10:20.150 This is recursion again. 10:20.450 --> 10:22.790 So let's call this function and see what happens. 10:22.890 --> 10:33.570 Green No dy no yes we would have seen things that are which is here because we'd run businesses. 10:33.700 --> 10:43.120 OK so let's see how this works toward bringing 10 8 0 which are all the left to children. 10:43.210 --> 10:46.690 Then we go to nine twenty fifteen and twenty five. 10:47.280 --> 10:47.730 OK. 10:48.040 --> 10:55.030 So if you compare these with our example you will see that the implementation is going to the left first 10:55.300 --> 11:01.490 and then to the right well this is pretty much it actually. 11:01.500 --> 11:03.540 So let's review this. 11:03.630 --> 11:10.760 We create an oak tree which has the eastern method which is its items and also we have a print method 11:10.980 --> 11:12.810 which brings the whole tree. 11:12.840 --> 11:20.950 Now we also said that binary isn't very useful for efficiently looking for values. 11:20.970 --> 11:21.330 Right. 11:21.570 --> 11:32.430 So let's implement a method on the Node practical exists which even a value will say if that value is 11:32.430 --> 11:35.980 part of the tree or isn't right. 11:36.000 --> 11:38.640 So again it's pretty similar to print. 11:38.700 --> 11:42.490 First we need to make sure that the node is not empty or otherwise. 11:42.610 --> 11:45.060 If the road is empty there's no value. 11:45.060 --> 11:46.730 So this will be false. 11:46.730 --> 11:47.010 OK. 11:47.490 --> 11:56.000 Now if know the value is equal to the value that we're looking for in this case value plus true. 11:56.040 --> 12:03.410 So return true which means that yes the value is not what happened with my children. 12:03.450 --> 12:11.760 What I need to do is again in value lower or equal than you will never be equal actually because that's 12:11.760 --> 12:14.980 already very high here that the no value. 12:15.150 --> 12:21.550 That means I need to verify the existence with my left now with my left side. 12:21.570 --> 12:24.850 So I go to the left node and collect. 12:25.560 --> 12:33.030 Otherwise I'll go to the right side and call X's right yeah. 12:33.320 --> 12:36.230 I need to turn these OK. 12:36.670 --> 12:40.670 So let's read this function one more time. 12:40.680 --> 12:43.970 Even only something I assume I'm on the leaf. 12:44.150 --> 12:44.570 No. 12:44.590 --> 12:49.350 So there's there's no more no to verify the value wasn't found. 12:49.600 --> 12:55.360 Is the value that I'm looking for is the same then the notes value true value exist in my tree. 12:55.360 --> 13:01.420 And then we're doing the binary operation which is is the value that I'm looking for lower than the 13:01.420 --> 13:02.080 current one. 13:02.230 --> 13:02.850 Yes. 13:02.890 --> 13:04.450 So I'm going to the left. 13:04.490 --> 13:06.400 Otherwise I'm going to the right. 13:06.450 --> 13:08.350 Now let's try this out. 13:08.380 --> 13:16.490 Let's say you know it says let's say twenty five. 13:16.760 --> 13:17.430 Why not. 13:17.730 --> 13:19.880 Oh green line. 13:20.180 --> 13:25.970 And this should be true because I've already a certain value here and it's true. 13:25.970 --> 13:26.340 Right. 13:26.750 --> 13:37.340 Now let's try to look for a value that doesn't indexes which will be 26 and it's false. 13:37.340 --> 13:44.420 Now let me just remove this if we want to check the no that has been evaluated on the look up of this 13:44.420 --> 13:45.070 value. 13:46.040 --> 13:53.900 We could go to the sixth function and just print the value of the note here. 13:53.930 --> 14:01.120 This is just to make sure that we're not traversing the whole tree while looking at the value so ok 14:03.470 --> 14:09.510 for looking at value 26 we're traversing for no number 10. 14:09.560 --> 14:10.730 Which is the root node. 14:10.830 --> 14:13.990 No no 20 and no no twenty five. 14:14.540 --> 14:20.990 So we're not going through any of the smaller one which shows the efficiency of the binary tree. 14:21.380 --> 14:23.390 So this is it for this episode. 14:23.420 --> 14:29.300 And with it we conclude with the section number three which is data structures. 14:29.360 --> 14:36.830 I hope you've enjoyed and learn and see you on the next one which is the most exciting section of this 14:37.010 --> 14:37.970 course by.