1
00:00:00,780 --> 00:00:01,620
Hi everyone.

2
00:00:01,620 --> 00:00:06,570
In this video, let's start discussing a new data structure which is called trees.

3
00:00:06,600 --> 00:00:11,160
Now trees are a data structure which is made up of nodes just like linked lists.

4
00:00:11,160 --> 00:00:14,820
But over here these nodes are in parent child relationships.

5
00:00:14,820 --> 00:00:16,920
Now let's take an example to understand this.

6
00:00:16,920 --> 00:00:18,780
So over here we have a sample tree.

7
00:00:18,810 --> 00:00:22,740
Now you can see that this node over here is connected to these three nodes over here.

8
00:00:22,740 --> 00:00:24,960
So these are children of this particular node.

9
00:00:24,960 --> 00:00:27,990
And this node is the parent of these three nodes over here.

10
00:00:27,990 --> 00:00:30,420
So they are in a parent child relationship.

11
00:00:30,420 --> 00:00:33,240
Now let's go ahead and try to understand trees in a better manner.

12
00:00:33,240 --> 00:00:37,350
Now the top node in a tree is called the root node of the tree.

13
00:00:37,350 --> 00:00:41,130
And when you take a look at these nodes over here, they can take any value.

14
00:00:41,130 --> 00:00:44,100
It can be an integer, it can be a string, etc..

15
00:00:44,100 --> 00:00:49,620
And when you compare trees with linked lists, which is another data structure which we previously discussed,

16
00:00:49,620 --> 00:00:55,050
you can notice that linked lists are linear, but trees are non-linear because you can see that over

17
00:00:55,050 --> 00:00:57,570
here it's going in different directions right now.

18
00:00:57,570 --> 00:01:02,040
In the case of linked list, there was only one direction to move, which was going from one node to

19
00:01:02,040 --> 00:01:02,880
the next node, right.

20
00:01:02,880 --> 00:01:05,460
So this was how a linked list was going.

21
00:01:05,460 --> 00:01:07,290
Like if you follow the next pointer.

22
00:01:07,290 --> 00:01:11,520
But then in the case of a tree we can see that they are non-linear in nature.

23
00:01:11,520 --> 00:01:12,060
All right.

24
00:01:12,090 --> 00:01:16,440
Now let's proceed and understand some terminology relating to trees.

25
00:01:16,470 --> 00:01:18,990
Now we have already seen child children and parents.

26
00:01:18,990 --> 00:01:23,730
So for example this node over here is the parent of these three nodes.

27
00:01:23,730 --> 00:01:27,120
And again you can say that these three nodes are children of this node.

28
00:01:27,120 --> 00:01:28,950
So that's child and parent.

29
00:01:28,980 --> 00:01:33,420
Now when it comes to siblings these are just nodes which have the same parent.

30
00:01:33,420 --> 00:01:33,810
All right.

31
00:01:33,810 --> 00:01:35,760
And again we have already seen the root node.

32
00:01:35,760 --> 00:01:38,520
The root node is just the top node in the tree.

33
00:01:38,700 --> 00:01:39,150
All right.

34
00:01:39,180 --> 00:01:40,950
Now again coming to siblings.

35
00:01:40,950 --> 00:01:43,530
Siblings are just nodes which have the same parent.

36
00:01:43,530 --> 00:01:47,340
So we can say that this node over here three and two and five.

37
00:01:47,340 --> 00:01:49,530
So these three nodes are siblings.

38
00:01:49,530 --> 00:01:52,020
And then we have edges in trees.

39
00:01:52,020 --> 00:01:53,820
So edges are just connections.

40
00:01:53,820 --> 00:01:56,550
So for example you have one connection over here right.

41
00:01:56,550 --> 00:01:57,480
So this is an edge.

42
00:01:57,480 --> 00:01:58,620
This is a sample edge.

43
00:01:58,620 --> 00:02:01,770
And then finally we have a terminology called leaf nodes.

44
00:02:01,800 --> 00:02:05,760
Now leaf nodes are just nodes which do not have any children.

45
00:02:05,760 --> 00:02:08,970
So for example in this tree over here this is a leaf node.

46
00:02:08,970 --> 00:02:10,020
This is a leaf node.

47
00:02:10,020 --> 00:02:14,670
And this and this is also a leaf node because you can see they have no children.

48
00:02:14,670 --> 00:02:15,180
All right.

49
00:02:15,210 --> 00:02:19,980
Now let's go ahead and take a look at few constructions which are not trees.

50
00:02:19,980 --> 00:02:20,370
All right.

51
00:02:20,370 --> 00:02:23,340
So we have seen what trees are now to understand them better.

52
00:02:23,340 --> 00:02:26,190
Let's take a look at a few constructions which are not trees.

53
00:02:26,190 --> 00:02:29,190
So for example we have a graph over here.

54
00:02:29,190 --> 00:02:33,210
Again these are just graphs because graphs are just edges and nodes.

55
00:02:33,210 --> 00:02:35,940
So this over here is not a tree.

56
00:02:35,940 --> 00:02:36,840
Why is that so.

57
00:02:36,840 --> 00:02:41,790
Because in the case of a tree the node cannot point to a sibling.

58
00:02:41,910 --> 00:02:42,360
All right.

59
00:02:42,360 --> 00:02:45,870
So over here you can see that this node over here is pointing to a sibling.

60
00:02:45,870 --> 00:02:47,610
And that is not allowed in a tree.

61
00:02:47,610 --> 00:02:49,950
It can only move away from the root node.

62
00:02:49,950 --> 00:02:52,620
So every node can only point to a child.

63
00:02:52,620 --> 00:02:55,530
And the edge has to move away from the root node.

64
00:02:55,530 --> 00:02:59,520
So this is not moving away from the root node, this connection over here or this edge.

65
00:02:59,520 --> 00:03:02,100
So again that's why this is not a tree.

66
00:03:02,100 --> 00:03:03,660
And you can think of it in this manner.

67
00:03:03,660 --> 00:03:06,600
Also this node over here is having a connection to a sibling.

68
00:03:06,600 --> 00:03:08,850
And that is not allowed in the case of a tree.

69
00:03:08,880 --> 00:03:10,560
Now let's take another example.

70
00:03:10,560 --> 00:03:12,930
This over here is also not a tree.

71
00:03:12,930 --> 00:03:13,500
Why is that.

72
00:03:13,500 --> 00:03:18,090
So you can see over here this node is having two parents and that is not allowed.

73
00:03:18,090 --> 00:03:22,440
In the case of a tree every node is allowed to have only one parent.

74
00:03:22,440 --> 00:03:24,810
And also there are two beginnings for this.

75
00:03:24,810 --> 00:03:25,080
Right.

76
00:03:25,080 --> 00:03:28,620
So we have seen that the top node in the case of a tree is called the root node.

77
00:03:28,620 --> 00:03:30,480
But then over here there are two beginnings.

78
00:03:30,480 --> 00:03:31,740
So that is also not allowed.

79
00:03:31,740 --> 00:03:36,030
There can be only one beginning or one root node in the case of a tree.

80
00:03:36,060 --> 00:03:38,250
Now let's take a look at one more example.

81
00:03:38,250 --> 00:03:42,990
Now we can see that this individually is a tree and this individually is also a tree.

82
00:03:42,990 --> 00:03:49,140
But if you take these two together, this is not a tree because a tree cannot be disconnected.

83
00:03:49,140 --> 00:03:49,530
All right.

84
00:03:49,530 --> 00:03:54,360
Now again when we talk about graphs in the course, in the future part of the course, we will see that

85
00:03:54,360 --> 00:03:58,650
this is allowed in the case of a graph, which again is just nodes and connections.

86
00:03:58,650 --> 00:04:01,680
So you can notice that trees are actually a type of graphs.

87
00:04:01,680 --> 00:04:05,850
But then when it comes to trees, trees cannot be disconnected.

88
00:04:05,850 --> 00:04:08,010
So this over here is not a tree.

89
00:04:08,010 --> 00:04:08,400
All right.

90
00:04:08,400 --> 00:04:09,390
So let's summarize.

91
00:04:09,390 --> 00:04:11,340
We have seen that trees are rooted.

92
00:04:11,340 --> 00:04:13,500
So we have the root node over here.

93
00:04:13,980 --> 00:04:15,630
And then they are acyclic.

94
00:04:15,630 --> 00:04:20,400
Or they do not form a cycle because every connection is moving away from the root node.

95
00:04:20,400 --> 00:04:20,700
Right.

96
00:04:20,700 --> 00:04:25,260
If there was a connection like this and then probably a connection like this, we can say this would

97
00:04:25,260 --> 00:04:28,500
be a cycle, but then this is not allowed in the case of a tree.

98
00:04:28,500 --> 00:04:34,170
So every connection is moving away from the root node and therefore there will be no cycle in the tree.

99
00:04:34,170 --> 00:04:35,880
So trees are acyclic.

100
00:04:35,880 --> 00:04:41,640
And then we have seen that trees are directed or edges are pointing downwards as you can see over here.

101
00:04:41,640 --> 00:04:42,060
All right.

102
00:04:42,060 --> 00:04:44,280
And then trees cannot be disconnected.

103
00:04:44,280 --> 00:04:49,110
We have seen that something like this where you have one tree over here and then you have another tree

104
00:04:49,110 --> 00:04:49,980
over here probably.

105
00:04:49,980 --> 00:04:54,780
But then this together cannot be considered a tree because trees cannot be disconnected.

106
00:04:54,780 --> 00:04:59,250
And then we have also seen that every node can have only one parent.