In this lecture, will implement a tree and C_sharp does not provide a tree class to us. So, if you need a tree, you need to build one yourself. We'll start by looking at the tree node class which is of course a generic. It has three fields, it has the value we're storing in the node, it has a reference to its parent, and it has references to each of its children in a list. So, you can think of this as like a doubly linked list. Remember, a singly linked list, each node only points to the next node in the list, whereas in a doubly linked list each node pointed both to the next node in the list in the previous node in the list. It's actually helpful to have a node pointer to its parent as well as to its children. So, I have links both up and down the tree between the nodes in the tree. The constructor, we pass in a value and we pass in our parent. So, for the trees I've implemented, the nodes have to have a parent, and of course the root node in a tree will have null as the parent. But when we create a tree node that we're going to add to an actual tree, we want to indicate what parent that node has so we can hook it into the tree correctly. So, we set the value field and the parent field to the parameters that were passed in, and we create a new empty list of children. For the properties, we can get the value, we can both get and set the parent and we'll see where those things happen in the tree class, and we provide a Read Only list of the children of the node. And this is the same technique we used in our graph node class to provide a Read Only list of the children for a graph node. The AddChild method, make sure we don't add a duplicate child, we don't allow self loops. In fact, trees are acyclic, we can't have cycles in a tree, and we certainly can't have a cycle from a node to itself. So, we don't add the self as a child. But finally, if we can add a child, we add the child that was passed in to the list of children for this node. And we also set the parent for that child to this node, and then we return true. We might want to remove a child, and if we do, we check to make sure our list of children contains the child to be removed, and if it does, then we null out the parent for that child because that child is now parentless, because remember nodes in a tree can only have one parent. So, if we are disowning this child, if we're removing this child node as a child of this particular node, then that child no longer has a parent. And then we return the results of calling the list remove method for the child. If we get here, it means that the child that was passed in isn't a child of this node, so we return false, because we can't remove a child that we don't have. We also provide a Remove All children method, and that helps when we want to clear a tree so we can support garbage collection. And finally, we convert to the node to a string. And we do that by saying what the value of the node is, and what the parent of the node is. And so, it could either be that the parent node has some value, or it could be that the parent is in fact null like for the root node in the tree, and so we put null if that's the case, and then we append a list of all the children. The tree class is also a generic. It has two fields, a reference to the root of the tree which starts as null, and a list of the nodes in the tree which starts as an empty list. The constructor requires us to pass a value in, and that value becomes the root of the tree. And you'll notice that when we call the tree node constructor, we provide the value for the node, and we say null for the parent because the root of the tree doesn't have a parent node, and we add the root to the list of the nodes for the tree. For the properties, we let a consumer of the class get a count of the number of nodes in the tree, and we also let them get a reference to the root of the tree. Because it's very common, as we will see it when we do tree traversal, it is very common to traverse a tree starting at the root, and you have to have a reference to the root before you can actually do that traversal. We have a number of methods, we can clear all the nodes from the tree, and to do that we null the nodes parents and remove all children. So, this makes sure that there are no references between the nodes, so they can be garbage collected. And then we take all of those nodes out of the nodes list and reset root to null. So now, the tree doesn't have any nodes and doesn't have a root, but all those previous nodes can be garbage collected. When it's time to add a node to the tree, we make sure the node isn't null, because that would be so easy to add a null node to the tree. We make sure that the parent isn't null, because if the parent is null we're trying to add a second root to the tree, and that would not be connected to the rest of the tree, and our tree has to be totally connected. And finally, we also make sure that the set of nodes for the tree actually contains the parent. So, if the node is null, or the parent is null, or the nodes doesn't contain the parent, we return false. We can't add this node because it's defective in some way. So, here's where we access the parent property of a tree node. So, we move to the parent, and we access the list of children, and we check if that list of children contains the node we said we just want to add, because if that's true that means that this node is already a child of the parent, so we return false. And finally, we might be okay. And if that's the case, we add the node that was passed into the list of nodes, and we also call the AddChild method on the node's parent because we want to add this node as a child of the node's parent. Removing a node from the tree is the most complicated method we have here. So, if we pass in a null node to remove, we return false. We also check the special case where the node to remove is the root of the tree, because of it is, what we're really doing is clearing the tree. So, we just clear the tree and return true. The elese clause is the interesting part of this method. So, the first thing we try to do is we try to remove the node as a child of that nodes parent. And if that fails for some reason for example, this node isn't actually a child of the parent, then we're going to return false. So, we're doing some error checking along the way here to make sure each step of removing the node from the tree succeeds, otherwise we return false. After removing it as a child of the parent, we remove the node from the list of nodes for the tree. And again, if that wasn't successful we return false, and here's where we actually have some recursion. So, we check to see if we are actually a branch node. So, if the number of children we have is greater than zero, then we're actually going to recursively prune the sub-tree that is rooted at this remove node. Remember, because each node only has one parent, as soon as we remove this node, all the nodes that are a sub-tree rooted at this node are no longer reachable from the root. There's no other way to link into those other nodes starting at the root. So, we have to also prune each of those nodes out of the tree. So, what we do is we get the children off the node we're removing, then we put them in this list, and then we iterate over this list going backwards because we're going to remove stuff as we go along, and here's the recursive call. So, this is one of the reasons we covered recursion. We will use recursion here in our implementation of the tree class, and we also will use recursion when we do tree traversals in a couple of lectures. But this is the interesting chunk of this method, because we see recursion in action to prune that sub-tree. We can look for a tree node with a particular value and this should all look familiar to you. The only difference from what we've done previously is that we are actually allowing duplicate values in our tree, so we will just return the first node with the value provided that we find in the tree if we find one. And finally, we convert the tree to a string as well, and the root might be null so we have to check for that. If it's not null then we add the root value, otherwise we say the root is null, and then we go through the nodes in the tree and we append each of those nodes converting it to our string for the tree. And that's it for the tree class. To recap, in this lecture we saw how to implement both a tree class and the tree node class we need to support that, and we also saw recursion into action in the remove node method.
