Hacker News Reader

Comment by znfii | Hacker News Reader

Was it ever figured out what "invert a binary tree" means? At least I had never heard this term used prior to this incident. This has me slightly worried about this particular example somehow, and I'm not quite sure what to make of it...

View on HN

            2                             2        
           / \                           / \       
          /   \                         /   \      
         /     \                       /     \     
        1       3                     3       1    
       / \     / \                   / \     / \   
      0   7   9   1    reverse >>>  1   9   7   0  
     /   / \     / \               / \     / \   \ 
    2   1   0   8   8             8   8   0   1   2
           /                               \       
          7                                 7

— https://leetcode.com/problems/invert-binary-tree/description...

So several people replied with this same thing, which I have heard before being suggested. However, as I recall it at the time, if you tried to search for "invert binary tree" this term basically did not exist on the internet. I just tried searching on google with time set between 2000 and end of 2014 which seems to give similar results.

I guess I did not spell it out in my original post, but I always felt it might have been an intentional nonsense question intended to gauge how he would react to someone talking nonsense, or something like that, and not necessarily related to technical things. A sibling post of my original to suggest this was the case, without the weird detour through the term "invert binary tree".

Edit: Of course an alternative explanation is that the interview used another term and he then used the term "invert" on twitter.

Idk, this example at least has to me always felt like people who complain about not passing the driver's test coz they did some minor error and then forgetting to mention that they drove past a stop sign.

I'm not 100% sure about the inverting part, but at Google nobody ever told me to ,,fuck off'' and nobody would tolerate that language, and that person would get a serious talk from his/her manager, maybe even laid off instantly, especially if it's written.

I assumed it as taking a binary tree (L|R) and reproducing a tree that's (R|L). And if it is that, then writing out the algorithm on a back of a napkin just now was a pretty thought provoking exercise :)

It means to swap the left and right arm of each node. So you effectively "mirror" the tree.

Yeah, it's relatively simple once you come to that realization:

    TreeNode* invertTree(TreeNode* root) {
      if (root == NULL) {
        return NULL;
      }
      
      TreeNode* tmp = invertTree(root->left);
      root->left = invertTree(root->right);
      root->right = tmp;
      
      return root;
    }

It sounds a lot more complicated than it is.

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.

Invert a binary tree as in heapify it maybe because inserting occurs at the leaf not root? Is that what it means? Does it simply mean changing the insert criteria so that a<b is now b<a?

Reply on news.ycombinator.com