Basically what the title says. We're given an array of sorted ints and we need to return a count of the variations of BST that can be generated from it.

Ex for input {1,2, 3}, output would be 5

I pretty much blew it. I was able to start building them (pick one as root and generate tree taking the rest and left and right arrays) but wasn't able to figure out how to get the actual count. Close to the end the interviewer hinted it should be a product of the number of variations on the left and number of variations on the right. Posting here to share and see how easy the question really was.