TREE TERMINOLOGY - DATA STRUCTURES

[Music] hello friends welcome back to our Channel so so far we have seen the linear data structures the like arrays the Lincoln list and all these things so where the data is organized in a sequential manner so from today we will go with the nonlinear data structures so that means trace and graphs so here a tree is nothing but organizing the data in hierarchical fashion that means nonlinear it's not in a linear form nonlinear fashion that is in high lyrical fashion we will start with the things so a tree is nothing but the data which is organized in hierarchal fashion without any clothes region see for example let us take a simple example so this is called a tree this is called a tree because it is having the elements but not the total surface so if you have an edge between B and C if you have an edge between B and C then this is having a producer fence so this is not a thing right so that's why organizing the elements without any clothes or region or but without any closer to that we call it as a tree so here all the elements are represented as a nodes so similar to a legalist right so in the linked list also we are representing every element as it notes the if you consider an array we will call them as n elements if you consider a linked list we should call them as a note and similarly if you consider there is a tree we have to represent as a nodes so here also there are nodes now we will see the basic terminology of this t's and the basic technology so if you know the basic terminology of the trees then then this concept will be very easy for you for the next sessions first one node node so node means the element the element of a tea so it is an element of a tea is called a node so let us consider a tree a simple example for a tree so that with an example we can write everything okay so this is a simple tree okay this is also a simple tree right so a tree can have I mean number of elements a tree can have a number of filaments boy people should call the magic number of loads so every element so here the event of a tree is called as node so here the elements are a b c d e f g and h so all these are the nodes all these are the nodes of a take root node root node the starting node of a tree we call it as a starting element the starting node of tree is called root from where the branches occurs so here the starting node is yay so in the example yay isn't root low yeah is a root node and one more thing we'll have to remember every tree should have only one group so 3 is having 3 we have only one root role only one who put right next h edge so edge means a link or a connection between a Volvo to another floor see here we can see in different notes and all these nodes are connected by with the means of edges so here a B a and B are connected with the help of an edge yeah and C are connected with the help of an edge ba D are connected with the help of an it so H is a link or connection between two rules between two holes right it's a link or action between two rules now if our T is having yell nose our T is having n nodes then that tree cap will be having n minus 1 edges if a tree is having M nodes then it will be having n minus 1 edges right see let us consider within the example here the L is equal to number of moves is equal to 1 2 3 4 5 6 7 & 8 okay so 8 nodes are there now count the edges how the edges so according to our formula so if if it is having 8 notes it should have the 7 inches let us come so 1 2 3 4 5 6 & 7 so 7 inches right so if you need 3 is having with the N loops then number of edges for the tree will be n minus 1 right so this is called an edge parent parent node so parent nor means the Lord which is having branches that can be happened that that can be called as a parent so for example yeh node a is having two branches okay so a is having two branches so B and C B and C are the branches of a so that is why we can call a as a parent for B and C and C again B is having three branches so B is a parent say C doesn't have any branch so C we should not call C as a parent and similarly D is not having any branches so D is not called as a penned F is not having any branches so f is not a parent so G and hitch and also not a parent but he is having two branches so he's called a pair so from the top to bottom from the top to bottom if any node is having a branches then that node can be considered as a pent nor with branches some time to board our corner pins so here we can say yeah Billy e hot pellets are paid notes so we can call them as parent knows because he is having branches similarly B is having branches he is also having branches right so here a node can have a multiple branches that means a parent can have multiple chains see so these are the few terminologies node root node H period now we'll go with a cube or chain so after the parent we should call it as chain the next terminology is chain so chain means C which is having branches from bottom to top okay so Nord with edge from bottom to top from bottom to top or or branch of branches of paint we can call it as a check branches of North with the branches of parent we can call it as a chain so here see be is having a branch from bottom to top okay so this is a top to bottom so this is a top this is the bottom so be is having a branch from bottom to top so that's why we can call be as a chain see is having a branch from bottom to top so see scar the chain the EF our chains gh our chips so in this example B comma C comma D comma a comma F G and H all our chains so a node can have a number of chains a parent can have a number of chains okay siblings siblings sorry general English terminology that siblings means the children would share the same parent or a children of the same parent we call the magic siblings so change north of same parent chain notes of the same parent north we call them as siblings so in this example so be is a child of a sea state of you so B comma C are siblings similarly behavior she'll the same pattern so D comma Y comma F are siblings similarly GNH share the same pin gingka Mahesh are siblings okay hope you understood this one there's children of same parent with all the masses siblings next live live live floor leaf node means the node which is not having any chain is called a leaf node and more without chain nor without change nor the Lord without change node is called a leaf node so here you can observe the sea is not having any change D is not having any change yes is not having any tapes G and H all these nodes are not having any kind of children right similarly coming to the B B is having children d EF is having children G and H a is having children B and C right so the node which is without without any child change node that node we call it as a leaf node so in that example in our example c is in is node similarly D is a leaf node therefore the in-floor G and H are leaf nodes G and H are inference all these are done in flux right then next next one internal roots internal nodes so internal nodes means than all the rules other than leaf nodes are called as internal goes all nodes other than if notes so that means whatever the node which is having a child then that called as an internal node or we can say more with chain more with chain right nor with change nodes are called as internal goals so in this in this example we are having n number force with the children so Y is a change node sorry da is having the children so a will be the internal node similarly V is having the children B will be the internal node and E is having the children so he will be the internal node so here in this example so a B and E or a cup of notes okay a b e our internal nose next degree so degree of a node and a degree of a tip so maximum number of children the number of chain nose represents the degree of an old the numbers chain nose represents the degree of a node so for example degree of a degree of Yale so Nuria is having two children so degree of env2 similarly degree of B degree of B so B is having three children so the degree will be T and similarly the maximum the maximum degree of maximum degree among all nodes is a degree of fifty the maximum degree among all nodes is it degree of eight T so if you want to find the degree of complete tree that implies what the maximum number of degree among wall nodes so we have to find the degree for all the roles and the maximum degree where we have we get that will be the degree of a tree so here if you observe so degree of B is three so it is a maximum so in this example the degree of a tree the degree of victory will be three so simply we can say the node with a maximum number of children we can say it has a degree of a tree right so in the tree whatever the load which is having the maximum number of children that we call it as a degree of it tree right so if you count the number of Chinese rows for each node that will be the degree of control the degree of a node so this is called degree next eleven level of a tree so each step or each hierarchical in a tree will be count as a level so always the level starts from zero so every step or hierarchy in a tree is a level so level always starts from zero starts from zero and for every step every step or hierarchy every step or hierarchy level will be incremented by one see here if you observe here so this isn't level 0 this is at level 1 this is at level 2 this is okay from top to bottom the level will be zero level starts with a zero so all the children of a will be at the same level in one all the children of being see will be in the level two and all the children of de F will be at level three so we call it as a step or hand so every step or every high-ranking simply we can call it as an identity right so every hierarchy of a tree is counted as a level so level starts from zero so keep on going the hierarchy the level will be also incrementing by one so here in this example the level of the tree the level of a tree is three right because it is having three hierarchies from the roof node zero so always the hard level of a root node is zero right the level of root node zero right so from the zero we have to increment the levels from each and every hierarchy so zero one two and three so in this example the level of at a is T now someone more think is high hi so here the height means so we have to find the height for a particular load so for a particular node the height means the longest path from a leaf node to that particular node is called a head so longest path from leaf not to that node is hi-c for example if you want to find the height of B height of a B then C from the leaf node the longest path from the leaf node so leaf nodes are znh from the leaf node you have to find the path or the number of edges so here there are two edges G to E and E to be G to E and E to be two edges are there from the leaf node H there are two edges are there so that's why we can say the height of B is 2 and similarly height of EA if you hide if you can say hi Toph yay there aren't leaf nodes C is having I mean there is a leaf node C and there is a leaf node G and H from this leaf node C there is only one edge and from the leaf of G there are 1 2 3 edges so we have to consider the longest path height of phase 3 so there is a slight difference between the level and height right so here the height will be specifically specified for a particular node so that's why we have to find the longest path from a leaf node to that particular node for which we have to find the height so that is called a height right so hope you understood this one next depth depth so here also the same thing but here the depth is the longest path from root to that node so from top to bottom so here the height will be calculated from bottom to that particular node right so here the depth means we have to consider the root node to that node that particular node for which we are going to find the path so the longest path from root node to that load so depth is also for calculating the node so depth of e depth of e names finding the longest path from root node to G that means yay-yay to be B to e so here the depth is to deduct these two similarly the depth of G is root root to that node so 1 2 3 G's 3 right so hope you understood this one depth of B from root to that node root to that node so only one H so depth of bees okay so the depth is the longest path from root node to that particular node next see but but part means the sequence of notes from source to destination sequence of moves from root to leaf we can simply set from bluefruit to live or a source to destination so here see a path means the part of a to G is so A to B B to e e to G so this is called a path this is called pop a sequence of nodes from source to destination this is called pop next subtree the load with the children will always form say something like soul or with the children forms something I see here in this example we can say I will once again it right here see this is a dream and this one's another dream and this forms another so this is one pretty and this is a another subtree and this is a under circle right so hope you understood this one so every node with the chain olds on a subtree and this is also mentioned so you simply we can say this is also isn't okay so so these are the basic terminologies we have to know before going to the Tris concept so these are the all the basic terminologies so right once all these terminologies so hope you understood all these things so the root node more age-group Lord edge parent parent nor change nor siblings live Lord internal modes internal loads degree level height depth but something so all these are the basic technologies of a3 so we have seen all these things so hope you understood this basic terminologies so if you are having any doubts regarding this basic terminologies so feel free to post your doubts in the comment section so that definitely I will try to clarify all your doubts so let us stop here and in the next session we'll go with one more concept on trees so if you really understood my sessions like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 55,925

Rating: 4.9127183 out of 5

Keywords: sundeep, saradhi, kanthety, data structures, arrays, lists, stacks, queues, trees, graphs, primitive, non primitive, linear, non linear, linked lists, ds fundamentals, ds basics, nodes, self referential structures, dynamic memory, structures, list creation, list display, lists operations, interview, placements, cse, edge, connection, parent, child, leaf node, internal, depth, height, level, path, sub tree, degree, siblings, root node, level of tree, tree terminology, hierarchical

Id: -LYhq4WZ04s

Length: 30min 11sec (1811 seconds)

Published: Mon Jul 08 2019