Iterate over a Binary Tree
This program was originally written for a Google interview as an example of iterating over a binary tree.
This is not quite a solution to the problem as stated. The original problem was to create an iterator to pass over the binary tree. I do not know enough C++ (yet) to do this, though I might look at some of the iterators in the standard template library to see how this is done.
So I implemented an iterate function to iterate over the tree. It is not an iterator as invoking the function will always iterate over all the nodes in the tree. If I implement it as an iterator I will have to keep some state information representing the current position in the tree - this is probably as simple as keeping a pointer to the last tree node returned returned by the iterator. I would also implement a ++ operator, addition and subtraction operators, and a begin method.
This code has been compiled and tested using Gnu g++ on a Macintosh.