Meta Interview Question
Create an iterator class for a tree. The iterator should traverse the tree using in order traversal. Implement the constructor and next functions.
Interview Answer
Anonymous
Feb 13, 2015
I traversed the entire tree in the constructor using recursion to implement DFS, storing nodes in a circularly linked list as I went along. I kept track of what node the iterator currently was on, and just returned node->next for the next function. Having to store the entire tree was very inefficient.