Comment by vkou
8 years ago
Until I throw this test case at you:
TreeNode testRoot = new TreeNode();
testRoot.left = testRoot;
invertTree(root); // Stack overflow.
But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.
That ought to be done in a separate validation step, and/or the tree object should enforce its invariants.
(I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)
I argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a properly formatted integer gracefully.
Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.
Sure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.