Up until now, we have discussed purely linear or flat data structures. Today, we are going to discuss a new series of data structures that provides us the ability to have complicated data and relationships such as a parent, child, and sibling relationships. This data structure is called a tree, let's dive into what this means. This is one of my favorite trees in the world, and this tree maps all of the Mario games that were created in the entire Nintendo franchise until 10 years ago. As part of this tree, you can see that there's an original game that included Mario, that was Donkey Kong. From there, there's a ton of different games that run the entire lineage of Mario game going only to Mario Galaxy, and there has been probably 100s of games since then. So, seeing this Mario family line, we see a starts with a single node and really these are precursors to the actual first Mario game, and the first true Mario game, he is really here, we can really consider this the root of the tree. From there we can see that the root of the tree has several branches, my personal favorite is Super Mario Brothers RPG, great classic if you've ever played it. But let's actually talk about trees not in terms of a specific tree, but terminology that can apply to every tree possible. In fact, this video is just going to talk about the terminology so that after this point, we can be very clear when we're describing this data structure. Every single element in our tree, we're going to call a node, and we're going to always denote a node with a circle. So, you'll see here's a tree and in this tree we have a number of nodes. Nodes are always connected to another node by an edge. In a tree, an edge will always be directed, and we'll always be directing the edge away from a root. In computer science we often say that we grow trees backwards because it will represent a tree with the root on the top compared to our normal tree, then will grow out by going down instead of going up. But you can really think of original tree just turned upside down. So, a tree must always contain a single root node and the root node must have no incoming edges. So, the topmost node of the tree as we draw it has nothing coming into it, all it has is nodes going out of it and every tree must contain a single root. So, there's only one node that has no incoming edges, and that node must be the root. Nodes that have no outgoing edges are called leaf nodes. These are at the base of our tree and these, just like a normal tree which got a common leaves and these leaf nodes can be found at any level, but the only requirement is they have no outgoing edges. In our trees, our node will store our data. So, here in this tree we've stored the first 10 or so letters the alphabet, in this tree, the nodes contain the data. Edges on the other hand, are often never labeled and they contain no data. In fact, we'll identify the edges just in the names of the nodes that they connect. For example, this edge from K to M, we'll just call this KM because this is the edge that starts from K and goes to M, and it connects the node K and the node M. So, we will very rarely ever name an edge, and our edges will never contain data. All of the data that we're going to store in this data structure will always be in the nodes. Every node except for the root node will have something we refer to the parent node. This works just like a family tree. One level up from you and the tree is going to be your parent. For example, the parent of B is A since B has an incoming edge from A. The parent of K is D. Looking at the incoming edge again, parent of L is also D. On the flip side, a node's children are the node that have that node is a parent. So, it's possible for a node to have anywhere from zero children to an infinite number of children, where every node but the root has just a single parent. So, notice that node A right here, node A has three children. Node C, a leaf node has no children. So, leaf nodes have no children because they have no outbound edges. M right here has just a single child. So, we see a node that has three children, a node that has one child, and a node that has six children. So, these type of relationships on the tree work just like an ancestral tree, and all of the ancestry terms that you're used to really do apply to the trees. Siblings. A sibling of a node is something that's on the same level and shares a parent. So, B and D are siblings. An ancestor works just like a normal family tree, a grandchild, or a grandparent works just like a family tree. You can have multiple grandchildren just like you could have in a family, but because our nodes don't actually marry, you only have a single grandparent. Finally, we want to define exactly what it means to be a tree. In a tree, three conditions have to be true. The tree must have a root, the tree must have directed edges, and the tree must not contain a cycle. So, what this means is if I were to have a edge from M to D, suddenly, we can travel from D to K to M, back to D in this big loop. If we ever have a loop, we're no longer a tree. So, long as all of our edges travel down a level deeper, sooner as all of our edges are down, then we can never have a loop, because to have a loop, we have to move an edge up. So, as long as all of our nodes face down, we can easily check any diagram and say, okay, yes, all of the nodes edges face down, therefore, we must have a tree. We said this tree is a rooted, directed, acyclic structure, and we'll explain what this means more as we talk about general trees or graphs later in this class. So, the big things takeaway is trees are formed with nodes and edges, trees must be directed, rooted, and acyclic, and the relationship between nodes and a trees follows a classical ancestry pattern, it's got parents, it's got children, it's got grandchildren, it's got a grandparent, it has ancestors, and it has descendants. All of the terms that you're accustomed to from your own family, we're going to use here in computer science. So, now that you have your tree terminology, let's dive in and look at particular types of trees that are particularly useful as a data structure. I'll see you there.
