from Hacker News

Invert a binary tree on LeetCode

by ripitrust on 6/13/15, 9:14 AM with 49 comments

Inspired by Max Howell's tweet

by de_Selby on 6/13/15, 10:27 AM
The problem wasn't to just reverse the nodes, it was to re-sort it:
> @rogerdai16 to min-max the tree, ascending to descending.
https://twitter.com/mxcl/status/608891015945170944

by mgraczyk on 6/13/15, 10:21 AM

In fairness to Google, the question is pretty darn simple...

    def invertTree(self, root):
        if root is not None:
          tmp = root.left
          root.left = self.invertTree(root.right)
          root.right = self.invertTree(tmp)
        
        return root

by meggar on 6/13/15, 12:03 PM

This looks like it works

    <html>
    <style>
    pre {
        -webkit-transform:scaleX(-1);
        -moz-transform:scaleX(-1);
        -ms-transform:scaleX(-1);
        -o-transform:scaleX(-1);
        transform:scaleX(-1);
    }
    </style>
    <pre>
         4
       /   \
      2     7
     / \   / \
    1   3 6   9
    </pre>
    </html>

by diminish on 6/13/15, 10:40 AM
What's hard is to have necessary CS background to understand what "inverting a tree" as a term means. As a non-CS major, I don't know what they use it for as a "term" and it evokes several things I can do with a tree as an outsider. So interviewers can quickly eliminate me as a non-CS. How to invert a tree on a whiteboard? Use a mirror.
by cousin_it on 6/13/15, 11:52 AM
At first I thought that he was given a slightly harder problem: given a binary tree and a particular leaf node of that tree, return another tree that's graph-isomorphic to the original, but has that node as the root. (You can visualize that as picking up the tree by a leaf node and shaking it, then reinterpreting the result as another tree.)
by raverbashing on 6/13/15, 10:44 AM
Too bad the website requires you to sign up to run your solution.
But it's an interesting concept, I've had to use a similar one in the past for a job interview.
by djhworld on 6/13/15, 11:22 AM
I've enjoyed many of the responses on this topic, some people like to use it as a self congratulatory platform to express their position that the solution is trivial and "any engineer should be able to do it like me" with a piece of example code, while others use it as a soapbox to moan about the scourge of the tech interview process.
by AYBABTME on 6/13/15, 10:36 AM
This topic has spilled too much ink.
by ripitrust on 6/13/15, 10:39 AM
C++ Solution here :
TreeNode* invertTree(TreeNode* root) { if (root) { TreeNode* temp = root->left; root->left = invertTree(root->right); root->right = invertTree(temp); } return root; }

by wfunction on 6/13/15, 10:30 AM

Considering the answer is 1 line, I doubt I would have hired him either...

    def inverse(t): return Node(inverse(t.r), t.v, inverse(t.l)) if t else t

or if you must do it in place, 3 lines...

    def invert(t):
        if t: (t.l, t.r) = (invert(t.r), t.v, invert(t.l))
        return t

by ExpiredLink on 6/13/15, 10:45 AM
>> You have not signed in, cannot submit your code.</a>

by adnanh on 6/13/15, 11:39 AM

My JS

  var invertTree = function(root) {
      if (!root) return null;

      root.right = [invertTree(root.left), root.left = invertTree(root.right)][0];

      return root;
  };

by jbrooksuk on 6/13/15, 10:58 AM
As a non-CS major, what is inverting a binary tree used for? Google just keeps bringing me back to Max's tweet, or blog posts about it.
by fishnchips on 6/13/15, 1:22 PM
This is just flogging a dead horse.