1
00:00:00,430 --> 00:00:07,720
‫So now we're going to do our introduction to trees, and we're going to create our trees with nodes

2
00:00:07,720 --> 00:00:11,170
‫that are similar to a linked list node.

3
00:00:11,470 --> 00:00:16,630
‫The linked list node had member variables of value and next.

4
00:00:16,870 --> 00:00:22,540
‫So let's put this back and change this to a binary tree node.

5
00:00:23,140 --> 00:00:26,190
‫So instead of having next, we'll remove that.

6
00:00:26,200 --> 00:00:28,640
‫I will also change the color.

7
00:00:28,660 --> 00:00:34,720
‫I like to do that when I move to a new data structure so we can keep these things visually separate.

8
00:00:35,020 --> 00:00:44,740
‫But the binary tree node has two pointers left and right, so this is still similar to the linked list

9
00:00:44,740 --> 00:00:48,310
‫node, but instead of having one pointer, that is next.

10
00:00:48,310 --> 00:00:51,700
‫We have two pointers that are left and right.

11
00:00:52,120 --> 00:00:57,460
‫So I'm going to put this back and I'm going to shrink this down and move this up here.

12
00:00:57,730 --> 00:01:05,230
‫And as you would expect, these pointers can point to other binary tree nodes.

13
00:01:05,650 --> 00:01:14,200
‫And if we look at this as we have previously with nodes, that this is similar to nested unordered maps,

14
00:01:14,770 --> 00:01:18,490
‫these three nodes would look something like this.

15
00:01:19,290 --> 00:01:21,420
‫So let's put this back.

16
00:01:22,160 --> 00:01:28,550
‫So the way we've designed our nodes with value left and right, they're set up where they can only point

17
00:01:28,550 --> 00:01:29,960
‫at two other nodes.

18
00:01:30,590 --> 00:01:33,740
‫So if you set it up that way, it's going to be a binary tree.

19
00:01:34,250 --> 00:01:36,680
‫But trees don't have to be binary.

20
00:01:36,680 --> 00:01:43,010
‫You could have this 0.23 nodes or 100 nodes or have it where you could point it to unlimited nodes.

21
00:01:43,430 --> 00:01:49,940
‫But for what we're going to build, each node can only point to two other nodes.

22
00:01:50,360 --> 00:01:57,530
‫And then, of course, these new nodes that we've added can also point to two other nodes themselves.

23
00:01:58,140 --> 00:02:00,180
‫So now let's look at some terminology.

24
00:02:00,510 --> 00:02:05,960
‫This tree here is what is called full and a full tree.

25
00:02:05,970 --> 00:02:10,830
‫Every node either points to zero nodes or two nodes.

26
00:02:11,160 --> 00:02:13,320
‫So if you do something like this.

27
00:02:14,050 --> 00:02:21,220
‫Now you have a node, the seven node that only points to one node, so it is no longer full.

28
00:02:21,790 --> 00:02:22,990
‫So let's remove that.

29
00:02:22,990 --> 00:02:24,100
‫Make it full again.

30
00:02:24,900 --> 00:02:28,320
‫And if we remove these two, it is still full.

31
00:02:28,380 --> 00:02:30,630
‫But it is also something else.

32
00:02:30,660 --> 00:02:32,700
‫It is perfect.

33
00:02:33,200 --> 00:02:34,590
‫With a perfect tree.

34
00:02:34,610 --> 00:02:40,600
‫Any level in the tree that has any nodes is completely filled all the way across.

35
00:02:40,610 --> 00:02:44,090
‫So this is also a perfect tree.

36
00:02:45,070 --> 00:02:51,400
‫But if we remove these two, it is no longer perfect, but it is still full.

37
00:02:52,450 --> 00:02:54,370
‫So let's bring these two back.

38
00:02:54,950 --> 00:02:58,280
‫So a perfect tree is also something else.

39
00:02:58,670 --> 00:03:01,040
‫It is complete.

40
00:03:01,490 --> 00:03:09,200
‫So with a complete tree, you are filling the tree from left to right with no gaps.

41
00:03:09,900 --> 00:03:17,010
‫So if we add a node down here, it is still complete because we are filling the tree from left to right.

42
00:03:17,750 --> 00:03:21,980
‫But it is no longer full and it is no longer perfect.

43
00:03:22,460 --> 00:03:29,120
‫If we add one more node like this, filling this from left to right, it remains complete, but it is

44
00:03:29,120 --> 00:03:31,340
‫now also full.

45
00:03:31,940 --> 00:03:36,650
‫But it is not perfect because we haven't filled it all the way across.

46
00:03:36,660 --> 00:03:43,010
‫So if we do this now, it is full and perfect and complete.

47
00:03:43,990 --> 00:03:46,580
‫So let's focus in on this tree.

48
00:03:46,600 --> 00:03:48,580
‫Drop some of these off.

49
00:03:49,390 --> 00:03:53,110
‫So this note here is a parent.

50
00:03:54,060 --> 00:03:56,820
‫Of these two child nodes.

51
00:03:57,360 --> 00:04:04,020
‫These two child nodes, because they share the same parent are also called siblings.

52
00:04:04,720 --> 00:04:08,980
‫And every node can only have one parent.

53
00:04:09,340 --> 00:04:17,680
‫So if you see something like this where a node has more than one parent than it is not a tree.

54
00:04:18,190 --> 00:04:19,660
‫So let's put this back.

55
00:04:20,610 --> 00:04:26,100
‫And child nodes, of course, can also be parent nodes.

56
00:04:26,890 --> 00:04:30,310
‫Now these nodes at the bottom, they don't have any children.

57
00:04:30,310 --> 00:04:34,990
‫And a node that doesn't have children is called a leaf.

58
00:04:36,560 --> 00:04:37,220
‫All right.

59
00:04:37,220 --> 00:04:39,260
‫That is our intro.

60
00:04:40,290 --> 00:04:41,310
‫Four trees.