Bonus points for building a #lang for expressing trees and operations on them.
(note: this probably wouldn't actually get you bonus points, and might result in my wildly gesticulating to get your attention to try to drag you back to the actual interview)
A Google interviewer expects you to ask questions and clarify any simplifying assumptions you may have made.
For eg: Are you assuming right at the beginning that the entire tree fits in memory? If so, Google interviewers expect you to clarify that at the beginning. They might later ask you to modify your solution for cases where your assumptions don't hold true.
From what I know, the biggest mistake people make during tech interviews with the big 5 is directly jumping to solutions without probing deeper. At the scale at which the big 5 operate, many routinely simple assumptions can be problematic.
How about just working with the original tree the way it is and just traversing it in reverse order, if necessary.
I would probably ask if this is in-place or do we treat the input tree as immutable.
…that's what the parent comment is implying. Ask questions and don't assume things.
Asking too many questions sounds like you're trying to delay coding something up.
Suppose you just ask questions and they pile on more the requirements. Then the combination of requirements makes it so hard that you can't really code anything on a whiteboard. You're hosed.
If you incrementally prototype, at least you arrive at the same point having some iterations of code on the whiteboard.
Trust me, the interviewer is never gonna pile up requirements on you. In fact, they are trained to ensure that what they ask can be completed in the time allotted (with time to spare for candidate's questions). More often than not, when you ask clarifying questions, you will end up with a much different problem (and sometimes simpler) than what you expected.
> Asking too many questions sounds like you're trying to delay coding something up.
No it doesn't.
> If you can code a prototype as fast as asking question, why not. Code it up and then ask, "how about this: what requirements are missing from this that require changes or a rewrite?"
This is terrible, you are now making the interviewer do your work. You need to tell the interviewer what the boundary conditions of your solution are. That gives valuable data about your understanding of the solution space.
To clarify, by "what requirements are missing" I don't mean "what is wrong with my code" (as in, in what way does it not meet the requirements that were already given; please debug my code for missed requirements). Of course the properties of the solution are clear and remarks are made about that in the course of writing it up and discussing. The "what requirements are missing" question is purely about new/different requirements.
In my experience, if you write boilerplate you'd need to write anyways while asking these questions interviewers don't hold it against you.