3/26/15 - Tree Isomorphism

Today, Sam and I worked on UMD contest problem 4 from 2013, Tree Isomorphism. Basically, it gives you two string representations of trees, which could have any number of child nodes, and asks you to develop an algorithm to determine whether the trees have the same "structure", disregarding the actual data of the nodes.

First, we developed a TreeNode class, and started writing an algorithm to check if the trees were the same. Originally I figured we could just do a traversal of each tree and see if the connections were the same, but Sam pointed out that this approach would only work if the trees had the exact same structure in the exact order, which isn't necessarily the case. Instead, we wrote a recursive method that would generate all the possible orderings of child ListNodes for each parent ListNode, in a tree. Then each of these permutations was checked against the other tree, because if they were isomorphic, one of the permutations of tree A would eventually be an exact match for tree B.

The method generating all the permutations was the most difficult part, and we ended up having to look up how to do this as a hint. What our finished product did was traverse the nodes from root to leaves, and removing one element at a time from the list of nodes, then generating all permutations of the remaining nodes by making a recursive function call until that had been done for all elements.  The element that had been removed initially was then stuck back onto the beginning of the list.
It was tough, but Sam kindly helped me through it and did a good job of letting me think for myself. Recursion is something I have a lot of trouble picturing in my head, so hopefully I will have some more time to really understand how our permutations method works (In theory I understand it, but I'm not sure I could explain it to someone–I think my explanation in this post is probably missing some things)

Sam also re-wrote the permutations method in python, which was much easier to read. He also showed me the yield keyword in python, which is something I had come across in ruby but never really understood. Basically it is used with what is called a generator, a class that is iterable and generates values on the fly. Each time the code calling the generator increments, the next yield statement is evaluated and the value is sent to the function calling the generator.

It looks like yield in ruby is a bit different. Instead of being used to generate data to be iterated over, yield statements in ruby act as a way to pass data into a block that has been passed to the function. I actually don't like this, because it's all very implicit and hard to understand (at least as someone unfamiliar with this behavior). If you're unfamiliar, in ruby curly braces can be used to pass blocks of code into functions, so the statement foo {...} passes the code block {...} into the method foo, even though foo isn't defined to take any arguments.