Ask HN: Have you ever needed to invert a binary tree at work?

I asked you to invert a binary tree because I was asked to invert a binary tree. My father was asked to invert a binary tree. My father's father was asked to invert a binary tree.

Charles Babbage asked Ada Lovelace to invert a binary tree before he agreed to let her work on his Analytical Engine.

In his famous resume, Leonardo claimed knowledge of "efficient methods of turning a bifurcated assembly of facts upon itself, and other procedures useful in the arts of arranging and displaying facts."

It's tradition.

https://en.m.wikipedia.org/wiki/Ada_Lovelace

https://duckduckgo.com/?q=resume+of+leonardo+da+vinci&t=fpas...

I've used trees for data, but never had to invert one.

TBH asking that kind of question at interview is a big red flag for me, means that they don't understand how to interview tech people and therefore probably don't understand how to manage tech people.

0, but you need it to get work.

Just be pragmatic about it. The same way you've learned a lot of crap at school for nothing, do you expect that in the job market it would be any different?

The world is fucked up, the earlier you internalise this in yourself, the less you suffer.

As a professional developer, if I am faced with the task of dealing with binary trees at work, I would never:

- implement my own binary tree

- implement my own "invert a binary tree" algorithm

Reasons:

- my own implementation would be way worse than any other open source implementation (which has been reviewed extensively) in terms of: performance, number of bugs, correctness

- it would be a hell to maintain for future developers that have to maintain my code

- it just makes sense. Well understood algorithms do not require re-implementation

No, however, please note the following:

Companies, like customers, have requirements for their needs. If a company needs a potential employee to know how to invert a binary tree then it's in their right to find one.

In Google's case, as you're probably alluding to[0], although I might be mistaken, they've always had the reputation for seeking the best qualified people[1] for their work. I mean look at who's working for them - there's a lot of well-known people in their respective fields that are working for them.

Moreover, I think that the point of these tests is to help assess a potential employee's abstract thinking. And, probably, to understand one's thought process behind the solution - if there's one - to the given problem. (Which, by the way, might be helpful if you're trying to solve AI - something that's right up in Google's alley ;).

Despite the backlash over this, I believe companies will keep doing these types of tests for a long, long time. I don't think this is going away that easily. And I also think that, in the future, these tests might be done in a way you won't even know you're being tested for.

[0] - https://twitter.com/mxcl/status/608682016205344768

[1] - I understand that "best qualified" here might mean different things for different people, but you should take it literally, that is, people who are above the average in terms of abstract thinking. I suggest you read How Google Works[2], they've coined the term Smart Creative which is kind of(?) related to this.

[2] - https://www.howgoogleworks.net/

Inverting a binary tree doesn't achieve anything; the organization is basically the same, being a mirror image, and so doesn't shed any new light on the data.

If you ever have to maintain a code base that happens to invert binary trees, find a way to nuke that code. Whatever needs the binary tree backwards should just process the original order backwards. Then you can say you once needed to remove a silly binary tree inversion at work.

Even reversing arrays and linked lists is suspicious.

Lisp code sometimes does a nreverse pass due to pushing items onto a stack while processing, which reverses their order.

I've never had to reverse an array in C or what have you.

I recall that the block sort algorithm does some clever things with multiple reverses of subranges of an array.

So I had to look up what 'invert a binary tree' meant. I was thinking make the leaves roots and the root a leaf, which made no sense.

So flipping the left and right, no I have never had to do that. I have had to write algorithms that processed the tree in infix, prefix and postfix order. And I have had to do it backwards, which is kind of the same but I never changed the tree for that.

As far as an interview question it is testing 2 things, 1) do you even know what a binary tree is, 2) are you comfortable with recursion. And in my case 3) are you willing to admit you do not understand and need an explanation.

From an interview perspective, all 3 are viable questions.

No and that's not the point. The point is knowing the application of that algorithm or the other.

But I also never had the need for its application, maybe I had and missed it :)

What does that even mean? Putting it upside down? But that's just the exact same graph, so a no-op operation? Come to think of it, I wrote a plenty of no-op methods in my career...

How about we do that in Lisp, and then apply the invert function to its own source code?

  1> (defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree)))))
  invert
  2> (invert '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  ((((nil (((nil ((nil (nil (nil . tree) . car) . invert) (nil (nil . tree) . cdr) . invert) . cons) . tree)
           (nil . tree) . atom) . if)
     nil . tree) . invert) . defun)

A Lisp tree structure can be regarded not as a binary tree, but as an n-ary tree; under which we can come up with a different semantics for inverting:

  3> (defun invert2 (tree)
       (if (listp tree)
          [mapcar invert2 (reverse tree)]
          tree))
  invert2

Now for comparison, we apply that to the original invert:

  4> (invert2 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  (((((tree car) invert) ((tree cdr) invert) cons) tree (tree atom)
    if)
   (tree) invert defun)

That's actually halfway readable.

Okay, now let's crank up the stupid knob to about 7.5.

  5> (defun invert3 (tree)
        (cond ((listp tree)
               [mapcar invert3 (reverse tree)])
              ((symbolp tree) (intern (reverse (symbol-name tree))))
              (t tree)))
        
  invert3
  6> (invert3 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
  (((((eert rac) trevni) ((eert rdc) trevni) snoc) eert (eert mota)
    fi)
   (eert) trevni nufed)

and finally to 11:

  12> (defun invert4 (tree)
        (let ((tree-picture (with-out-strlist-stream (s)
                              (print tree s))))
          (each ((line tree-picture))
            (let* ((rl (reverse line))
                   (sb (mapcar (relate "()" ")(") rl)))
              (put-line `@{sb -78}`)))))
  invert4
  13> (invert4 '(defun invert (tree)
       (if (atom tree)
         tree
         (cons (invert (cdr tree)) (invert (car tree))))))
                                                                   trevni nufed)
                                                        (eert mota) fi) (eert)  
                                       ((eert rdc) trevni) snoc) eert           
                                    (((((eert rac) trevni)                      
  nil

Look, text-wise left-right mirror image of the printed version of the tree!

Never had to create one, let alone invert one.

I have inverted a binary tree out of fun. But if you are less strict about left/right, you have to do exactly nothing.

No, I did have to do depth first search with backtracking (e.g. once at node go one up and take node with lowest value).

I guess its a matter of perspective