TREE DATA STRUCTURES | What is Tree? | DSA Course | GeeksforGeeks

Key Takeaways

hello everyone my name is Karan masu welcome to this video so in this video we are going to discuss about trees so what are trees trees are nothing but basically you can say graphs which contains n nodes and N minus one edes and it is also connected okay so tree is nothing but graphs it is a special type of graphs with n number of nodes n minus one number of Ages and it is connected okay now what do I mean by connected connected means if there is a path between each and every pair of vertices then that is called connected if there exist a pair of vertices or no such that there is no path between them then it is that graph is not called connected for example uh here in this graph I not saying this is a tree but in this graph if we check for connected between any two pair of vexes we have at at least one path for example between 1 and 2 1 and 3 1 and 4 2 and 3 2 and 4 3 and four right so this is a connected graph for example if I have something like this then here there is a path between one and two but the there is no path between 1 and three and two and three so this is not connected okay so if a graph contains n nodes n minus one hedes and if it is connected then it is called a tree okay now let's understand some more things about a tree before that let me just draw a tree okay so let's say this is One Tree okay so let's say this is a tree now how many nodes are there here 1 2 3 4 5 6 7 8 9 so my n is how much n also this is a connected graph there is a there is a path between each and every pair of vertices also there must not be any self Loops or parallel edges okay so what are self loops Loops so if this is a node and if there is a h to itself this is called self Loop and if between two nodes there are multiple edges then these are called parallel edges okay there is nothing like that this is a tree if you cross check there will be n minus one that is eight number of edges for example 1 2 3 4 5 6 7 and 8 okay so N - 1 is equal to 8 okay so this is the tree now uh if I tell you about some of the definitions then the top node is called the root node okay and uh this node is called root node all the leaves which do not have children the nodes which do not have children are called Leaf nodes okay these are called Leaf nodes who further do not have a children and the other nodes which are not Leaf so non-leaf nodes these are also called internal nodes okay these are also called as internal nodes another thing is uh a sub part of that is called a sub tree for example this is a sub tree if you look here there are four nodes and three edes and there is a path between each and every pair of node so this is called a sub tree okay now uh uh the direct node which is below it so starting from root uh 90 is directly below 100 so 90 is called the child of 100 okay 80 is called the child of 100 60 is called the child of 80 and so on also 100 is called the parent of 90 100 is also called the parent of 80 150 is called the parent of 160 and so on okay then uh what else can we say see uh for a particular node all the nodes which are below it are called descendants so for example for 80 60 70 and 108 are descendants for 100 90 80 60 70 108 200 150 160 all are descendants okay for 90 2 200 150 160 all are descendants okay these are called descendants okay one more terminology that is ancestors so for a particular node it's parent then uh parent of its parent then parent of parent of its parent and so on all of these are called ancestors for example for 70 uh 80 comma 100 are called ancestors for 150 for 160 uh 90 100 and 150 are called ancestors okay and so on so this is the general definition and some terminologist associated with trees now there is something called n AR trees so now let's have a look at that and then also uh look at a particular type of that okay so when do you say a anary tree when if or node can at Max have n children then it is called n AR tree okay if node can have ATX and children it is called aner tree okay uh so it can have no children or one children or two children or up to ATX Nary trees okay now among the Nary trees the most used one and the most famous one is the binary tree also for anary tree we can also say the degree of uh the tree is N means the maximum number of children any node of can have is n okay so we can also say degree of the tree is n binary tree means maximum number of children can be how much two so the degree of the tree is how much two okay so for example we have 10 we have 11 we have 12 we have 13 we have 14 is this a binary tree yes why because this has two children this has two children this has zero children okay is this a binary tree yes this has one children one is also allowed but if this a binary tree no more than two childrens are not allowed this is not a binary tree this is a binary tree now if we talk about the uh some basic applications of B uh trees then what is the basic application of a tree uh basically you can store hierarchical structures I'm not sure about the spelling but you understood right so what does it mean by hierarchical structure for example uh this is a particular manager and these two people directly report to that person then these two people directly report to this person this person directly reports to this person so under this manager all these people are there under this person these two are there and this person reports this and so on so it is a kind of hierarchical structure okay so this is a common application of uh binary tree now how do we represent binary trees so there are basically two ways of representing a binary tree representation of a binary tree okay uh I think this looks like f so I'll change it representation of a binary tree so there are two ways One is using the structure or pointers or you can say class so you structures or class and another is using arrays okay uh so whenever we are uh you know talking about binary tree or binary search tree then structures are used and there are also cases where we use arrays because that is more convenient to use like uh there are binary trees used in uh segment Tre okay then it is also used for Heap right so in all these cases we use uh arrays okay now uh what is the difference between these two structures so let me tell you so another first one is the structure representation right so we basically make a node which contains such a structure for example uh this is my node with value 10 this is pointing to the left child and this is pointing pointing to the right child this is a node with 20 this is pointing to a right child whose value is let's say 30 okay and let's say these two are null means they they are not pointing anywhere else this is also null okay then let's say this is uh let's say 50 this is pointing here with 60 and this is pointing here at uh 90 okay and all these remainings are null okay let's say so this is a binary so the structure of one node is something like this you have a node value you have a left pointer and you have a right pointer so you can say struct node you have int data then you have struct node pointer to the left node with respect to C++ in Java you you will have reference and you have struct node pointer right okay so for a particular node uh this is one node okay this is the structure type which we can call node okay we defined it as node you can see here node there is a data integer type you can have anything else also depending upon your data then there is a pointer to structure node type only and it is called left so this is called left and it is also a pointer to the structure node type and this is for left child and this is for right child which is called as right so this is one structure this is the structure representation when we talk about binary tree and binary search trees we use this another is array representation okay this we use while using segment trees or heaps Etc okay so what does array representation say uh so let's say uh your root node is at index zero okay your root node is at index zero then for the node with uh node number I the left child is at node number 2 I + 1 and right child is at node number 2 I + 2 okay for example uh if uh let's say this is my graph okay 10 20 30 40 50 60 okay this is the graph let's say so uh this is the root node with zero index so left child would be uh 2 into 0 + one that is first Index right child will be 2 into 0 + 2 that is second index the left child of one will be 2 into 1 + 1 that is third Index right child will be 2 into 1 + 2 that is fourth index here the left child is see since it's array representation we cannot miss out on this element but it will have garbage value so left child will be uh this index is two so 2 into 2 4 + 1 5 okay not five this is not the value this is the index and the right side will be at sixth index so I can represent it using an array having six indexes where the first value is 10 this is 20 this is 30 This is 40 This Is 50 this is some garbage value and this is 60 so this is your binary representation of uh sorry this is the array representation of this binary tree okay so that's all about the some basic things of trees uh then particularly anary trees uh then in that binary Tre specific case and the two different types of representation now in the next video we will solve some question based on this thank you