The Problem

Well this happened a year back but the problem was interesting, so I decided to post about it. Here's a little backstory. During the initial few months on my job, a senior called me and gave me a hard problem. It was based on a requirement for a project. They had a page with 4 menu items, on clicking any one of those items the person should go to a screen with another 4 menu items, these items had no particular relationship and were quite random. This can be seen in the diagram below:

One of the solutions being discussed was to use 47 if conditions, yes I counted. This would be especially bad because a small change in requirements would lead to huge amounts of changes in the code.

Part 1 - Convert the problem to a Tree Structure

After wracking my brains for some time, I came up with a solution that involved trees. So, I converted the above image into a tree, it would look something like this:

menuItems = {
  "item1" : {
    "item3": {},
    "item4": {},
    "item5": {
      "item3":{},
      "item4":{},
      "item6":{}
    },
    "item6": {}
  },
  "item2":{},
  "item3":{},
  "item4":{}
}

In this code, menu item 1 would lead to menu item 3, item 4, item 5 and item 6, item 5 leads to item3, item4, and item6. I got the menu items through Object.keys().

Part 2: Going to the selected element in the Tree

This is the easiest part of the problem, since I could find the clicked element. After this, I just found the next part of the tree, using the history of the previous items that were clicked. So this would be something like:

path = ['item1'] /* Path stores the items that were clicked
 and the order in which they were clicked */

function getCurrentMenu(){
   let current = menuItems
   for (item of path){
      current = current[item]
   }
   return Object.keys(current); /* Returns the list of items
   for the menu */
}

After this, for selecting a particular element I just pushed it to the path.

function addToPath(item){
   path.push(item)
   return path
}

Part 3: The back button problem

All this is well and good, but what if the user presses a back button? The screen should be able to render the buttons in the same way. The tree only points in one direction. Hence, for solving this I made use of the path that was being stored. I could just pop the last element in the array and then traverse the tree again. This would be something like:

function goBack(){
   path.pop()
   return getCurrentMenu();
}

Conclusion

This was a simplified version of the problem that I solved. Here's some code in Angular in case you are curious. All in all not an extremely hard problem, but I found it really hard at the moment. Well that was all about a real world example of using trees.

I would love to hear about the instances in which you have used trees or graphs in your code, let me know down in the comments.