In this lesson we are going to talk about working with tree-like data that's represented in documents stored in MongoDB. And specifically we're going to look at how we can deal with simple trees that have one way links. And then we're going to see some of the problems with that. And then we're going to see how we can use the aggregation framework to transform these singly linked trees into complex trees. And then we can see some of the benefits that we have with doubly linked trees for performing complex analysis. And while this lesson is on trees, in reality this lesson is on how to use graph lookup in a practical way, so you can apply it for recursive data structures, like trees. Okay, first we're going to do some setup, here we're going to go ahead and make sure we have the right dependencies installed and imported. And then we're going to connect to our MongoDB Atlas cluster. And here we'll be using the product categories collection. Which is a data set full of product categories that's akin to large online retailers. Here we're going to go ahead and issue a basic query, where we look for all the product categories that contain the word cat. We're going to use a regex to perform this. And we're then going to go ahead and return all these results and shove them into a DataFrame, so we can look at our data. And here are a whole bunch of other categories which all have the parent of cat supplies. I'm going to go ahead and use an open source library here called ETE3 for visualizing this tree. This content of this cell doesn't really matter that much, it's just so that we can go ahead and see how this tree looks. And while this does have some tree-like characteristics, there's a problem here. Which is that every node is a leaf node, reports directly up to a different parent category, and then there isn't really a root node here. And so to kind of better illustrate this, here's what we would like it to look like, where here we have all of our leaf categories following up to cat supplies, and then cat supplies follows up to its parent, pet supplies. And so today we're going to try to use graph lookup to model our data in this way, and moreover not only add these parental lengths we're also going to try to add child links so that we can do some more interesting analysis with this data. And so, like I said before, this is really an excellent use case for graph lookup, so here I'm going to go ahead and look for the product category Cat Toys. And then starting with Cat Toys, its name, I'm going to look for documents whose parent has that name, and then recursively just fetch those documents names. And a connect on documents whose parent field matches those names. And we'll call all those documents ancestors, because we're basically building out the ancestry graph here, right? And we're just going to continue doing this until we have no parent. When we execute this, and print it out, you can see that's pretty much what we get. Here we started with Cat Toys, we then have Cat Toys, which is kind of annoying, and we'll look at how to get rid of that in a second. But then we can see that Cat Toys parent is Cat Supplies, which is right here. Whose parent is Pet Supplies, which is right here, whose parent is Animal & Pet Supplies, which is right here. And then we end there because that has no parent. So we now have all of the parent documents, so from here we should be able to fill out the rest of the tree. But before we can do that, we first need to go ahead and remove this duplicate document right here, that's really referring to the same thing. And we can achieve that by using the set difference operator. And here we're going to remove nodes where the parent matches either its name or none in the case where the parent is actually the root ancestor, and the parent field is null. And when we execute this and print it out, and here you can see we have Cat Toys whose parent is Cat Supplies. And we have all of Cat Toys ancestors with Animal and Pet Supplies, Pet Supplies, and Cat Supplies. But we want to go ahead and keep that parental information, but more over we want to go ahead and try and calculate all of these node's children. So, we can really have a doubly linked tree.
