Introduction to Trees (Data Structures & Algorithms #9)

Key Takeaways

hey everyone in my last few videos i made a q a website for quarters and i still work on it from time to time but in this video i decided to switch topics and restart my data structures and algorithms series now in a previous video which i published a long time ago we learned the linked list data structure it looked like this one where we had a bunch of nodes that are connected to each other in a single direction and each node in the structure had a class like this it's called node and it has two attributes uh integer data and next which is also a node now a tree is a similar data structure to a linked list and the only difference is that in a linked list each node can only link to one other node but in a tree each node can link to multiple other nodes so here's one example of a tree as you can see each node here is linking to multiple nodes here each node is linking to at least three other nodes and so for this particular structure the class of each node might look like this one as you can see this one is called node again and it has four attributes uh integer data just like before sometimes this one is called value but we're calling data here and we have three children uh all of them are nose and so for example if you look at this particular node here the three children are set to these three other nodes and if you look at this node right here this one has only two children this one and this one so if you want to express that in code you can just set the two of the children to those nodes and the last child to null or none to show that it doesn't exist and if you look at this node it doesn't have any children so you can set all of these children knows to null or none depending on the language that you're using now let's take a look at another example of a tree so this one is drawn from top to bottom instead of left to right but it has the same kind of structure the more important difference is that each node has almost two children here so the class of each node might look like this one instead as you can see we have integer data just like before but now we have only two children which we're calling left and right and just like this when a tree has at most true truth it's called a binary tree now to help you understand what a tree is exactly we're going to call this little game called is this a tree basically i'm going to show you a structure and you just need to answer if it's a tree or not so let me start with this one this one uh doesn't have integers inside them instead it has strings but of course it's still a tree and what about this one well it's a linked list but it's also a tree and the way i think about it is that each node could have multiple children just like that but it just doesn't so it's kind of a boring example but technically speaking it's also a tree and what about this one well it might look like a tree but it's not because one constraint of something being a tree is that there are no two references that link to the same node and these two references violate that condition and what about this last one well again it violates the definition of being something being a tree for the same reason these two references point to the same node so it's not a tree and another way to see that this is not a tree is that it has a cycle here and whenever there's a cycle that's not a tree so you might say well what is a tree exactly then well a tree is a structure in which there are nodes that are connected to each other and there's a way to go from the root node to every other node in the structure so the root node in this particular tree is this one and there's a way for us to get to every other node from the root node in this structure and it's the same thing with this tree or this linked list there's this root node and there's a way to get to every other node from the root node but as soon as there are two references in this structure that refer to the same node for example this one then it's not a tree anymore so that's basically what a tree is and by the way the root node of a tree is a node without any parents so what that means is that whatever the root node is no other node refers to that one okay now that you hopefully have a clear idea of what a tree is let's practice using a tree with this problem you're given a tree for example this one with the root being here and this is a binary tree so the class of each node will look like this it has an integer data and it has two children left and right and the problem is writing a function which we're going to call find sum which takes the root of this tree as the input and returns the sum of all the values within the street so if you're given this particular root you want to be able to return 20 from this function because we have 2 plus 3 plus 5 plus 6 plus 4 which is 20. and try solving this problem in of and in time where n is the number of nodes in this tree okay and here's my solution and by the way if you want to try running my solution in either python or java you can find that at this url csojo.io tree like i said before we're calling this function find sum and it's taking the root of whatever tree that you're given and we're going to implement this function recursively here and the first thing we're going to do is we're going to define the base case and that's going to be when the given root is null or none which is that the given root is just an empty tree for example this empty tree right here then the sum of all the values in this empty tree is of course zero so we want to return zero in that case and otherwise uh for example if we're given this blue height right here in this recursive function then the sum of all the nodes in this tree is the sum of this current value plus the sum of all the nodes in the right subtree and the sum of all the nodes in the left subtree we can express that with this one line here we're returning the current value or root.data plus the sum of uh all the nodes in the left subtree so let's find sum of red dot left and the sum of all the nodes in the right subtree so let's find some of that right this function would only take of n in time to execute where n is the number of nodes in the given tree and let's think about why well first we need to count the number of times this function is going to be called and that's going to be the number of nodes in the given tree because for each node this function is going to be called once plus all the empty nodes or these empty trees that i didn't draw earlier in this representation of the tree and so this function is going to be called at most about 2n times or of 2n times which is the same thing as of n times and so this function is going to be called of n times and each time this function is called let's think about how how much time it takes to execute well if you look at each line uh if you look at this line it only takes a constant amount of time or of one because we're simply checking uh this simple if condition and it's the same thing as this line it only takes off one in time returning zero and this line as well we're simply adding up these three numbers so once we have the results for these two recursive calls adding up these three numbers would only take off one in time or a constant amount of time and so each time this function is called it only takes one and it's called o of n times so multiplying them together we get the total amount of time this function takes to execute or the time complexity of this function and that's going to be of n now that's it for this problem and my introduction to trees but if you need more practice using trees and there's another interesting problem that i think is much harder and it's a problem i talked about a while ago as a coding interview question so i'm gonna put a link to that video in the description below anyway thank you as always for watching my videos and i'll see you guys in the next one