Invert a binary tree on LeetCode

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

by ripitrust • 11 years ago

34 49 11 years ago

Inspired by Max Howell's tweet

mgraczyk• 11 years ago

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

microtonal• 11 years ago

Indeed, it's not a difficult question.

I think people were making fun of Google, because it is a caricature of their whole interview process.

If a large number of your engineers is using Homebrew, having its developer is an asset for many different reasons (e.g. influencing the focus of the project, getting formulae in that interest you, or simply improving a tool that is important to your productivity). But no, they reject him because he cannot invert a binary tree.

It's like throwing one of the better offenders out of your soccer team, because he cannot substitute as a goalkeeper.

wfunction2• 11 years ago

It's more like not letting the CEO of your soccer ball manufacturer play on your team because he can't kick a soccer ball.

onion2k• 11 years ago

Having the developer of Homebrew as an employee is only an advantage if you want to influence it's development, and if the developer is happy for his application to be influenced by his employer rather than the Homebrew community as a whole.

In fact, I would see Google hiring the leaders of open source projects in order to influence the direction the project takes as a problem. Sponsoring an open source project is brilliant, and Google are great at that, but buying influence over it is completely different and (potentially) an issue that would lead to people forking the project.

crdoconnor• 11 years ago

I think people were making fun of Google, because it is a caricature of their whole interview process.

To be honest, it kind of makes me wonder about the kind of code Google has, if this is a measure of a good coder. Are low level algorithms haphazardly re-implemented in python everywhere there is a need for one?

I've seen lots of code like that before. I was very unimpressed.

tjscanlon• 11 years ago

Iterative solution:

    def invertTree(self, root):
        queue = []
        if root is not None:
            queue.append(root)
        while queue:
            current = queue.pop()
            current.left, current.right = current.right, current.left
            if current.left is not None:
                queue.append(current.left)
            if current.right is not None:
                queue.append(current.right)
        return root

seivan• 11 years ago

Not sure why, but I'd feel iffy iterating on a list while mutating its content.

But I guess it's file while ignoring the order of the items, and just caring if it's containing items or empty.

Carry on :)

cousin_it2• 11 years ago

Any particular reason why you're using an array as a stack (LIFO) but calling it "queue" (FIFO)?

TheLoneWolfling2• 11 years ago

Better solution:

    def invertTree(self, root):
        queue = []
        if root is not None:
            queue.append(root)
        while current is not None or len(queue) > 0:
            while current is None:
                current = queue.pop()
            current.left, current.right = current.right, current.left
            if current.left is not None:
                if current.right is not None:
                    queue.append(current.right)
                current = current.left
            else:
                current = current.right
        return root

No needless enqueuing / dequeuing of things unless you need to. As a bonus, if the nodes maintain a count of how many children the have overall you can always recurse on the smaller child first and use less memory.

alexchamberlain• 11 years ago

Very interesting that the 3 answers here are 2 Python and 1 C++; I feared the world had descended into a JS downward spiral, but clearly not.

TN1ck• 11 years ago

I am your fear:

var invertTree = function(root) {

    if (!root) {
        return root;
    }
    
    var left  = root.left;
    var right = root.right;

    root.right = invertTree(left);
    root.left  = invertTree(right);
    
    return root;

};

andresmanz• 11 years ago

That was my fear, too. And I also will go with C++ first.

api• 11 years ago

It's not the difficulty people are whacking, but the practice of white board coding.

sltkr• 11 years ago

Btw, Python has nifty multiple assignment, so you can write the swap simply as:

    root.left, root.right = (self.invertTree(root.right),
                             self.invertTree(root.left))

(Parentheses added to break over two lines.)

aidos• 11 years ago

That was my immediate thought too. It's nice to think of those 2 operations as an atomic unit.

Freaky2• 11 years ago

Same in Ruby, but it doesn't need the parens to cross lines:

   root.left, root.right = invert_tree(root.right),
                           invert_tree(root.left)

de_Selby2• 11 years ago

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

SamReidHughes3• 11 years ago

I can't stand this. That's an equally intelligible description of the problem as the original.

de_Selby2• 11 years ago

Well it's a 140 character description from someone who's probably feeling a bit emotional. I'm sure he got a clearer problem description in the actual interview.

falcolas3• 11 years ago

I have to admit, the idea of swapping children on all of the nodes would not have come to me immediately as a solution for reversing the sorted tree - I have not been exposed to that kind of application before, and haven't spent a lot of time thinking about that kind of problem.

One more for the toolbox, I guess.

blahblah3• 11 years ago

It sounds like the problem may have been to convert a min heap to a max heap?

wfunction2• 11 years ago

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

AYBABTME• 11 years ago

This topic has spilled too much ink.

ExpiredLink2• 11 years ago

It's Google, it must be important!

falcolas3• 11 years ago

Its prevalence suggests that it's a pretty big issue that many interviewees face, and nobody has the answer on which is the best approach for hiring competent developers at scale.

ripitrust• 11 years ago

C++ Solution here :

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

diminish• 11 years ago

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.

logicchains• 11 years ago

I like the solution a friend suggested: flip the interviewer upside-down.

vishnuks• 11 years ago

I would go for flipping the White Board.

SamReidHughes3• 11 years ago

I don't think anybody was told "invert a binary tree" in the interview room.

adnanh2• 11 years ago

Matter of fact: https://twitter.com/mxcl/status/608682016205344768

raverbashing• 11 years ago

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.

caf• 11 years ago

There's a bugmenot login that works.

ExpiredLink2• 11 years ago

> You have not signed in, cannot submit your code.</a>

aaggarwal• 11 years ago

You can use http://ideone.com, it doesn't require you to sign in to execute your code and allows almost every language.

jbrooksuk2• 11 years ago

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.

jbrooksuk2• 11 years ago

I assume it's for sorting (and ordering) algorithms?

djhworld• 11 years ago

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.

falcolas3• 11 years ago

I've noticed that dichotomy as well. It seems to be splitting along culture lines - so one of these two camps would be right at home at Google, the other would be fairly miserable.

Of course, this creates its own issues related to creating and maintaining a mono-culture, but that's a topic for another thread.

adnanh2• 11 years ago

My JS

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

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

      return root;
  };

cousin_it2• 11 years ago

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

meggar• 11 years ago

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>

fishnchips• 11 years ago

This is just flogging a dead horse.

Invert a binary tree on LeetCode

Related Stories