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&#x27;s father was asked to invert a binary tree.<p>Charles Babbage asked Ada Lovelace to invert a binary tree before he agreed to let her work on his Analytical Engine.<p>In his famous resume, Leonardo claimed knowledge of &quot;efficient methods of turning a bifurcated assembly of facts upon itself, and other procedures useful in the arts of arranging and displaying facts.&quot;<p>It&#x27;s tradition.<p><a href="https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Ada_Lovelace" rel="nofollow">https:&#x2F;&#x2F;en.m.wikipedia.org&#x2F;wiki&#x2F;Ada_Lovelace</a><p><a href="https:&#x2F;&#x2F;duckduckgo.com&#x2F;?q=resume+of+leonardo+da+vinci&amp;t=fpas&amp;ia=web" rel="nofollow">https:&#x2F;&#x2F;duckduckgo.com&#x2F;?q=resume+of+leonardo+da+vinci&amp;t=fpas...</a>

I&#x27;ve used trees for data, but never had to invert one.<p>TBH asking that kind of question at interview is a big red flag for me, means that they don&#x27;t understand how to interview tech people and therefore probably don&#x27;t understand how to manage tech people.

0, but you need it to get work.<p>Just be pragmatic about it. The same way you&#x27;ve learned a lot of crap at school for nothing, do you expect that in the job market it would be any different?<p>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:<p>- implement my own binary tree<p>- implement my own &quot;invert a binary tree&quot; algorithm<p>Reasons:<p>- 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<p>- it would be a hell to maintain for future developers that have to maintain my code<p>- it just makes sense. Well understood algorithms do not require re-implementation

No, however, please note the following:<p>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&#x27;s in their right to find one.<p>In Google&#x27;s case, as you&#x27;re probably alluding to[0], although I might be mistaken, they&#x27;ve always had the reputation for seeking the best qualified people[1] for their work. I mean look at who&#x27;s working for them - there&#x27;s a lot of well-known people in their respective fields that are working for them.<p>Moreover, I think that the point of these tests is to help assess a potential employee&#x27;s abstract thinking. And, probably, to understand one&#x27;s thought process behind the solution - if there&#x27;s one - to the given problem. (Which, by the way, <i>might</i> be helpful if you&#x27;re trying to solve AI - something that&#x27;s right up in Google&#x27;s alley ;).<p>Despite the backlash over this, I believe companies will keep doing these types of tests for a long, long time. I don&#x27;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&#x27;t even know you&#x27;re being tested for.<p>[0] - <a href="https:&#x2F;&#x2F;twitter.com&#x2F;mxcl&#x2F;status&#x2F;608682016205344768" rel="nofollow">https:&#x2F;&#x2F;twitter.com&#x2F;mxcl&#x2F;status&#x2F;608682016205344768</a><p>[1] - I understand that &quot;best qualified&quot; 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&#x27;ve coined the term Smart Creative which is kind of(?) related to this.<p>[2] - <a href="https:&#x2F;&#x2F;www.howgoogleworks.net&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.howgoogleworks.net&#x2F;</a>

Inverting a binary tree doesn&#x27;t achieve anything; the organization is basically the same, being a mirror image, and so doesn&#x27;t shed any new light on the data.<p>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.<p>Even reversing arrays and linked lists is suspicious.<p>Lisp code sometimes does a <i>nreverse</i> pass due to pushing items onto a stack while processing, which reverses their order.<p>I&#x27;ve never had to reverse an array in C or what have you.<p>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 &#x27;invert a binary tree&#x27; meant. I was thinking make the leaves roots and the root a leaf, which made no sense.<p>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.<p>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.<p>From an interview perspective, all 3 are viable questions.

No and that&#x27;s not the point. The point is knowing the application of that algorithm or the other.<p>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&#x27;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?<p><pre><code> 1&gt; (defun invert (tree) (if (atom tree) tree (cons (invert (cdr tree)) (invert (car tree))))) invert 2&gt; (invert &#x27;(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) </code></pre> 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:<p><pre><code> 3&gt; (defun invert2 (tree) (if (listp tree) [mapcar invert2 (reverse tree)] tree)) invert2 </code></pre> Now for comparison, we apply that to the original invert:<p><pre><code> 4&gt; (invert2 &#x27;(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) </code></pre> That&#x27;s actually halfway readable.<p>Okay, now let&#x27;s crank up the stupid knob to about 7.5.<p><pre><code> 5&gt; (defun invert3 (tree) (cond ((listp tree) [mapcar invert3 (reverse tree)]) ((symbolp tree) (intern (reverse (symbol-name tree)))) (t tree))) invert3 6&gt; (invert3 &#x27;(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) </code></pre> and finally to 11:<p><pre><code> 12&gt; (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 &quot;()&quot; &quot;)(&quot;) rl))) (put-line `@{sb -78}`))))) invert4 13&gt; (invert4 &#x27;(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 </code></pre> 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&#x2F;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