Solution to 6: Folders

Every folder contains either 0, 1, or 2 immediate subfolders. If the folder has 2 immediate subfolders, one of them is named with a lowercase letter and the other with an uppercase letter. What we have here is a binary tree, with the direction of the child (left or right) specified by whether it is an uppercase or lowercase letter. Graphing out the whole tree in a grid, making sure to line up the columns, gives the following:



We read the tree through its columns from top to bottom and the columns from left to right. This is also known as a vertical order traversal of a binary tree. This gives: "Thrice the diameter of this tree". In the above example, I set lowercase to correspond to left children and uppercase to correspond to right children. However, if you did the opposite it will just result in the mirror image of the above picture and you just need to read the columns from right to left instead.

The diameter of a binary tree is defined as the longest path between any two nodes in the tree. This tree has a diameter of 17 so the answer is 3 * 17 = 51

51