3 ms·

What does it mean to "invert" a binary tree?

• tom_ 4y ago
  "Flip" or "mirror" is probably a better term. It seems the goal is to swap left and right: https://leetcode.com/problems/invert-binary-tree/ https://leetcode.com/problems/invert-binary-tree/
  • LanceH 4y ago
    I don't get why this one is the meme. Just because it's recursion? Because it's (nearly) pointless? There are so many other algorithms I find more difficult/more tedious.
    • plasticchris 4y ago
      I think it’s a meme because the home brew author tweeted that he was rejected by Google for failing to invert a binary tree.
  • kristov 4y ago
    Is there a practical reason to do this in a real-world program?
    • saagarjha 4y ago
      Sure, it’s the binary tree equivalent of reversing an array.
      • Tainnor 4y ago
        For large enough trees it's probably more efficient to instead just switch from preorder to postorder traversal instead of changing the whole tree.
• dekhn 4y ago
  Inverting a binary tree is easy; express the tree as a matrix (laplacian), invert the matrix, then convert that back to a tree. What the canonical question is asking is not inversion. Since too many people were memorizing inversion, I switched to asking how to evert a binary tree. This leads naturally into a discussion of the 1:1 relationship between complex numbers and cohomology sets, I figure if somebody can get that right, they can be a junior programmer on the team.