[Jasper_]

Has anybody ever figured out what "invert a binary tree" means? That came from Max Howell, and nobody else seems to have ever received that question.

The best anyone can figure out is that it's reversing the left and right branches, which seems like it's ten lines of code, at most?

[Liquix]

leetcode seems to agree with your definition [0]. the meme isn't to say that inverting a binary tree is particularly difficult - anyone familiar with coding challenges and trees could trivially produce a solution. the meme is more pointing out how ludicrous it is that senior/staff/principal interviews can hinge on these types of problems, despite the engineer proving their proficiency by doing something like running DOOM in typescript types or writing homebrew [1].

[0] https://leetcode.com/problems/invert-binary-tree/description...

[1] https://x.com/mxcl/status/608682016205344768

[devmor]

I think those challenges (especially leetcode) are heavily misused.

When my team conducts technical interviews, we are asking for a couple simple programming solutions - but we're asking because we want to hear the candidate talk through it and see what their problem solving process is like.

If you aren't evaluating based on conditions like those, I don't really see the value of coding questions.

[emmanueloga_]

I think brew's author point holds even if you replace "invert binary tree" with any other LC problem.

In terms of the problem itself, a binary tree can be expressed something like:

    type Node<T> = { value: T, left?: Node<T>, right?: Node<T> }

Given a root, you can invert it recursively with some code like this:

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

      // Swap!
      const tmp = root.left;
      root.left = invertTree(root.right);
      root.right = invertTree(tmp);

      return root;
    };

Or using an explicit stack:

    function invertTree(root) {
      const stack = [root];
      while (stack.length > 0) {
        const node = stack.pop(); if (!node) continue;

        // Swap!
        const tmp = node.right;
        node.right = node.left;
        node.left = tmp;

        stack.push(node.left);
        stack.push(node.right);
      }
      return root;
    }

I think without prep would be harder to come up with the non-recursive version.

[mirekrusin]

Maybe the catch was in saying that left right labels are arbitrary, could be called node1 and node2 as well, inverting is not necessary per se, just visit it in node2, node1 order if needs to be flipped - ie. no physical rearrangement is necessary.

[jerf]

Also the best answer to "how do you reverse an array". You don't. You just read it in the opposite order. Especially in any iterator-based language it should be trivial.

In a pure ASCII world, this doubles as "how do you reverse a string". In a Unicode world, the answer to "how do you reverse a string" is "you should never want to do that".

[ryanmcbride]

That's what it means, and people use it as an example not because it's like, some sort of super difficult unreasonable challenge, but because it's completely unrelated to the work you'd be doing on the job like 99.99% of the time. It's like interviewing for a line cook and asking them to make a spatula.

[pino999]

Depends on how you look at it, I guess. A binary tree has a couple of properties. Usually there is some ordering on the type. Something like: the element on the left is smaller than the element on the right. (e_L < e_R). Invert would be than turning the ordering into e_R > e_L. I guess this is the left and right branches exchange answer.

If you see a binary tree T e as some kind of function, it can test whether an element exists, a typical set operation. So f : e -> {0,1}, where (e,1) means the element is in the binary tree. (e,0) means it is not in the binary tree. All those (e,0) creates some sort of complement tree, which might also be seen as inverting it.

What would be really weird is seeing it as a directed acyclic graph and invert the direction of every edge.