Hi everyone.
In this video, let's start discussing a new data structure which is called trees.
Now trees are a data structure which is made up of nodes just like linked lists.
But over here these nodes are in parent child relationships.
Now let's take an example to understand this.
So over here we have a sample tree.
Now you can see that this node over here is connected to these three nodes over here.
So these are children of this particular node.
And this node is the parent of these three nodes over here.
So they are in a parent child relationship.
Now let's go ahead and try to understand trees in a better manner.
Now the top node in a tree is called the root node of the tree.
And when you take a look at these nodes over here, they can take any value.
It can be an integer, it can be a string, etc..
And when you compare trees with linked lists, which is another data structure which we previously discussed,
you can notice that linked lists are linear, but trees are non-linear because you can see that over
here it's going in different directions right now.
In the case of linked list, there was only one direction to move, which was going from one node to
the next node, right.
So this was how a linked list was going.
Like if you follow the next pointer.
But then in the case of a tree we can see that they are non-linear in nature.
All right.
Now let's proceed and understand some terminology relating to trees.
Now we have already seen child children and parents.
So for example this node over here is the parent of these three nodes.
And again you can say that these three nodes are children of this node.
So that's child and parent.
Now when it comes to siblings these are just nodes which have the same parent.
All right.
And again we have already seen the root node.
The root node is just the top node in the tree.
All right.
Now again coming to siblings.
Siblings are just nodes which have the same parent.
So we can say that this node over here three and two and five.
So these three nodes are siblings.
And then we have edges in trees.
So edges are just connections.
So for example you have one connection over here right.
So this is an edge.
This is a sample edge.
And then finally we have a terminology called leaf nodes.
Now leaf nodes are just nodes which do not have any children.
So for example in this tree over here this is a leaf node.
This is a leaf node.
And this and this is also a leaf node because you can see they have no children.
All right.
Now let's go ahead and take a look at few constructions which are not trees.
All right.
So we have seen what trees are now to understand them better.
Let's take a look at a few constructions which are not trees.
So for example we have a graph over here.
Again these are just graphs because graphs are just edges and nodes.
So this over here is not a tree.
Why is that so.
Because in the case of a tree the node cannot point to a sibling.
All right.
So over here you can see that this node over here is pointing to a sibling.
And that is not allowed in a tree.
It can only move away from the root node.
So every node can only point to a child.
And the edge has to move away from the root node.
So this is not moving away from the root node, this connection over here or this edge.
So again that's why this is not a tree.
And you can think of it in this manner.
Also this node over here is having a connection to a sibling.
And that is not allowed in the case of a tree.
Now let's take another example.
This over here is also not a tree.
Why is that.
So you can see over here this node is having two parents and that is not allowed.
In the case of a tree every node is allowed to have only one parent.
And also there are two beginnings for this.
Right.
So we have seen that the top node in the case of a tree is called the root node.
But then over here there are two beginnings.
So that is also not allowed.
There can be only one beginning or one root node in the case of a tree.
Now let's take a look at one more example.
Now we can see that this individually is a tree and this individually is also a tree.
But if you take these two together, this is not a tree because a tree cannot be disconnected.
All right.
Now again when we talk about graphs in the course, in the future part of the course, we will see that
this is allowed in the case of a graph, which again is just nodes and connections.
So you can notice that trees are actually a type of graphs.
But then when it comes to trees, trees cannot be disconnected.
So this over here is not a tree.
All right.
So let's summarize.
We have seen that trees are rooted.
So we have the root node over here.
And then they are acyclic.
Or they do not form a cycle because every connection is moving away from the root node.
Right.
If there was a connection like this and then probably a connection like this, we can say this would
be a cycle, but then this is not allowed in the case of a tree.
So every connection is moving away from the root node and therefore there will be no cycle in the tree.
So trees are acyclic.
And then we have seen that trees are directed or edges are pointing downwards as you can see over here.
All right.
And then trees cannot be disconnected.
We have seen that something like this where you have one tree over here and then you have another tree
over here probably.
But then this together cannot be considered a tree because trees cannot be disconnected.
And then we have also seen that every node can have only one parent.