This is interesting, I was asked this question in an interview for a Microsoft internship, but for a binary tree.