Comment by znfii

8 years ago

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...

11 comments

znfii

Reply
guessmyname  8 years ago 

            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...

  • znfii  8 years ago

    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.

    • xiphias  8 years ago

      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.

Posibyte  8 years ago

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 :)

gizmo  8 years ago

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

  • ezekg  8 years ago

    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.

    • 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.

      3 replies →

matthewaveryusa  8 years ago

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?