42: Collections: Left-Child Right-Sibling Tree.

A game that only has one character with one quest and with one shop that sells one item isn’t going to be very fun. That’s why you need to be able to work with collections of items. You have choices and this episode continues more than a week long exploration of collection types available. You’ll learn when to use each type of collection and why. Up today is another tree called a left-child right-sibling tree. I’ll explain what these trees are and then give you some guidance on when to use them. Here’s what a left-child right-sibling tree might look like when holding some folders. This example shows a root node “C:” with two children, “Program files” and “Windows”. The “Program Files” folder has its own folder for “Office”. A real file system will have a lot more folders but it will follow this basic pattern shown below: root -> node(C:) node(C:).leftChild -> node(Program Files) node(Program Files).parent -> node(C:) node(Program Files).leftChild -> node(Office) node(Program Files).rightSibling -> node(Windows) node(Office).parent -> node(Program Files) node(Windows).parent -> node(C:) Listen to the full episode or you can also read the full transcript below. Transcript Are you familiar with how to arrange your folders and files on your computer? You might have a single root folder on a Mac or Linux or several drive letters on Windows that are root folders. Inside a root folder, you can have other folders and files. And inside a regular folder, you can have other folders and files. This is a hierarchy. It starts with a single node and can branch out quickly, or go deep, or both. You might have just a few folders at the root level but then have some folder that contains thousands of folders or files. In a situation like this, you’re more concerned about the structure than sorting. That doesn’t mean that finding files is not important. You probably still want some other data structure to keep track of where files are overall. But you need a tree that can let you place a folder or a file in an exact place. This place may not have anything in common with other items nearby but that doesn’t matter. If the user wants to place a file inside some folder, then that’s where it needs to go. We can’t use a binary tree because it places items where it needs to based on some comparison. Maybe you could have a folder class that contains pointers for child folders. But how many child folder pointers do you need? You don’t know so this needs to be a collection. Should you put child folders and files together in this collection? Probably not because folders need to have the ability to contain other child items while files don’t. If both folders and files were in the same collection, then you would need some common interface for both of them. It’s better to keep child folders and child files in separate collections. How about using a couple vectors. One for folders and one for files? This would definitely allow you to keep track of a collection of folders and files at any given folder. Maybe this is exactly what you need. You can get very creative with just some vectors and your own classes. But the problem with this is that the overall structure switches back and forth between vectors and your own classes. If you later find that you need a similar structure for different classes, then you’ll need to implement all this all over again. And if you have code that’s designed to work with your folder and vector structure, then it will also need to be adapted to work with the new class and vector structure. What if you could create a collection type that allows you to represent a hierarchical folder structure and that would work with any class; not just folders? We’ll keep the files in the folder class because they’re not really part of the hierarchy structure. Although,