BST Sequences
This post is about a problem in the book “Cracking the Coding Interview” in chapter 4 “Trees and Graphs”. I’m writing this because I found my C# solution to be much clearer and concise than the one proposed in the book. I just hope that my solution is actually correct, otherwise I’ll have egg on my face!
The aim is to return all of the sequences of arrays that would produce the given binary search tree. I understood after sketching an example tree on the whiteboard that it required recursing through the subtrees, returning the resulting multiple sequences — with the left and right subtrees switching order to produce permutations. I believe this could be accomplished either breadth-first or depth-first, as long as each node is prepended to the result in order of traversal.
In this diagram, you can see that 3 and 10 could have been inserted in any order because 8 at the root forces them to be on the left and right respectively. Working further recursively you can see it holds true for each subtree.
Although I settled on the approach very quickly, the actual implementation took quite some time. Dealing with sequences of sequences turns out to be a bit mind-melting! One of the false paths I went down was looking up how to create all the permutations of a collection (with the output containing all of the elements of the original collection), nevertheless as we’ll see it was very close to the final solution.
Here you can see the code to create permutations, helpfully associated with a unit test. You can gather from the expected data how it progresses to achieve the result. The procedure is:
- For each element in the input collection x
- For each permutation of the input collection excluding x
- Prepend x to the permutation
It’s clear by looking at the first column (1, 1, 2, 2, 3, 3) that it’s taking each element (1, 2, 3) and prepending it to the permutations of the rest of the collection in turn. We just need to take care of the base cases: an empty list, in which case we return 0 permutations, and a singleton list, in which case there’s only one possible permutation.
Now let’s take a look at how to generate BST permutations:
I hope you’ll agree that it’s remarkably similar! We have the same two base cases: empty and single, where the solution is trivial. Then the remaining procedure is:
- From the permutations of the left subtree
- From the permutations of the right subtree
- Concatenate the left and right permutations and prepend the current node’s value
- Repeat step 3. but this time reverse the order of left and right
- Return the combined permutations
In fact, by changing the function to use arrays of nodes, rather than a single node each time, it looks even more like the standard collection permutation function:
The only difference here is that we need to recurse further for each subtree to generate the next collection, and then concatenate those results.
The proposed java solution from the book requires 56 lines of code, uses two recursive functions rather than one, and does a lot of juggling with mutable data structures. I will concede that they may have restricted themselves to using the broadest approach possible in order to feasibly implement in any programming language, although I don’t think there’s anything special about my solution that’s specific to C#.
