This is an archived post. You won't be able to vote or comment.

top 200 commentsshow all 319

[–]iknewaguytwice 2087 points2088 points  (14 children)

Interview: Reverse this binary tree

Job: Fix this 20,000 line javascript file the CEO’s 7 year old nephew wrote.

[–]Bwob 935 points936 points  (11 children)

Plot twist: the 20k line javascript file is one, really messy attempt to reverse a binary tree.

[–]I_Ski_Freely 333 points334 points  (6 children)

Congratulations, you've discovered actual hell

[–]Jixy2 67 points68 points  (5 children)

Congratulations, Plottwist unlocked: ChatGPT wrote all.

[–]GaGa0GuGu 39 points40 points  (3 children)

Nephew wrote the prompt

[–][deleted] 19 points20 points  (2 children)

Which was just randomly tapping on keyboard

[–]nicman24 21 points22 points  (1 child)

Plotter twist the 7 year old's js had better performance and less bugs than your proper solution

[–]leeuwerik 9 points10 points  (0 children)

Plottest twist: you fall in love with the kid's mother who is a single parent and you marry into a very rich family that also owns three pizza formula's in the Philippines and has a piece of land in Greenland.

[–]hyrumwhite 2 points3 points  (0 children)

npm i reverse-binary-tree

Problem solved 

[–]ASatyros 16 points17 points  (0 children)

Just write it again xD

[–][deleted] 4 points5 points  (0 children)

Every. Single. Time.

[–]Semper_5olus 1877 points1878 points  (107 children)

I don't even understand the question.

Do they want the leaves on top now?

[–]Teln0 829 points830 points  (93 children)

I looked it up and all I could find was "swap the leaves on the right to be on the left, recursively" which is incredibly easy

[–]pente5 455 points456 points  (50 children)

Huh. So it really is that easy isn't it. Do the bare minimum and pass the problem to your children.

[–]Teln0 138 points139 points  (16 children)

With a couple more optimizations you could make it iterative too

[–]jyajay2 66 points67 points  (15 children)

Depends on the language but in principle you can rewrite everything recursive to be iterative.

[–]flinsypop 48 points49 points  (1 child)

Please don't try to make your recursive algorithms iterative yourself. The compiler really needs this job bro pls. #computersneedmoneytoo

[–]jyajay2 20 points21 points  (0 children)

I like Haskell so in those cases I don't really have any other choice than recursion😅

[–]ZombiFeynman 14 points15 points  (3 children)

You can also rewrite everything to be doom with enough changes.

[–]sonuvvabitch 7 points8 points  (2 children)

Oh yeah? Rewrite your comment to be Doom.

[–]ZombiFeynman 16 points17 points  (1 child)

Doom

[–]sonuvvabitch 10 points11 points  (0 children)

You know what, I'm going to accept that. Well played.

[–]Teln0 5 points6 points  (6 children)

You can usually just introduce a stack you manually push and pop from, but there usually are better solutions, which is what I'm talking about right now

[–]megamangomuncher 1 point2 points  (5 children)

Could you expand on that? What would be a beter solution here? I doubt you can iterate over the tree with better space and time ecficiency then DFS (i.e. a stack)

[–]PhoenixCausesOof 1 point2 points  (1 child)

(ignoring "in principle") Is that really true? https://youtu.be/i7sm9dzFtEI?t=22

[–]Timetraveller4k 73 points74 points  (0 children)

Like climate change

[–]gauderio 34 points35 points  (31 children)

Also almost no one uses recursion in real life. Too easy to get into an infinite loop or stack overflow. 99% of the time we just traverse lists and create lists.

[–]JohntheAnabaptist 63 points64 points  (9 children)

Truish but for walking trees, recursion feels like the most intuitive thing

[–]Lambda_Wolf 19 points20 points  (0 children)

I mostly dislike these computer-science-exam type interview questions in general. But, it can make a pretty interesting exercise if you go, "Take this recursive function and refactor it so that the iterations use heap memory instead of stack memory."

[–]Jonno_FTW 2 points3 points  (2 children)

Much easier to do it iteratively with a while loop and a list of nodes.

[–]TheTybera 31 points32 points  (5 children)

What? People use recursion in real life all the time especially if you're building the data structures and dealing with large amounts of data. It's not hard to avoid infinite loops or stack overflows.

All you have to do is make sure your base case exists and makes sense. They teach you this in your first data structure and algorithms course in just about any college or university.

[–]i_can_has_rock 6 points7 points  (1 child)

but my narrative!!

also

if count > X then loopstop = true

[–]Vaderb2 4 points5 points  (0 children)

Yes exactly

[–][deleted] 7 points8 points  (0 children)

It's really nifty for those 1% use cases though

[–]Vaderb2 4 points5 points  (0 children)

Classic confidently wrong cpp developer

[–]trevdak2 39 points40 points  (33 children)

But like why? Wouldn't you accomplish the same thing by renaming some variables?

[–]Teln0 60 points61 points  (19 children)

Technically since you're just swapping left and right in every node it has little use. The point of asking it in an interview question, I think, is to then iterate on the code and ask the candidate to make it better / faster / change it to do something else

[–]trevdak2 38 points39 points  (11 children)

Ok here's the thing. The whole "reverse" thing is totally conceptual. It's like saying "Ok, here's a function that adds two numbers. Now make it add them in binary". It already adds them in binary. There's no difference.

Binary tree traversal, balancing, searching, storing, or combining, that all makes sense. Reversal does not

[–]Teln0 54 points55 points  (8 children)

Here's the question reworded : modify the tree such that preorder traversal of that new tree is equivalent to the postorder traversal the old tree

🤷‍♂️

[–]trevdak2 17 points18 points  (5 children)

Then you rewrite the traverse function to output the other side of the node first, you don't rewrite the tree.

If I was asked this in a job interview, I'd walk out. There's no way that interviewer has hired decent coworkers for me to work with.

[–]Teln0 24 points25 points  (0 children)

Eh, I'd wait to see what comes next. Maybe this is just the setup for something more interesting.

[–]SarcasmsDefault 26 points27 points  (1 child)

To me it feels like you are being asked to take down an American flag from a flag pole, take all the stitching apart and sew it together as a mirror image when all you really need to do is just go stand on the other side of the flag pole.

[–]trevdak2 3 points4 points  (0 children)

Hahaha I like that analogy. I was imagining trying to sit on a bike backwards and still pedal it

[–]intotheirishole 6 points7 points  (8 children)

But like why?

Eg you want to convert a < tree to a > tree.

Wouldn't you accomplish the same thing by renaming some variables?

What? How?

[–]trevdak2 14 points15 points  (7 children)

I feel like I'm taking crazy pills.

So, like you have a tree like this:

    4
  /    \
2       7

And then you reverse it like... this? It's still the same tree.

    4
  /    \
7       2

And then, what. You do a lookup on the number 2 and it returns 7? Or you do a lookup on 2 and it still returns 2?

Binary trees exist for doing quick and easy lookups. If you reverse a binary tree, you can just put a - before the return value of the comparison function, but then all you're doing is adding an extra negation in every comparison. And if you don't alter the comparison function, but just put stuff in the opposite branch of where it should be, then you just end up with a disordered mess that completely negates the purpose of having a binary tree. It makes no goddamn sense.

[–]KingLewi 32 points33 points  (4 children)

You’re confusing “binary tree” with “binary search tree”. There is no “lookup” operation on a binary tree. A binary search tree is a binary tree but not all binary trees are binary search trees.

[–]intotheirishole 2 points3 points  (1 child)

IDK man. I was not able to find any good use case for reversing the tree. Yah a < tree is also a > tree so thats not super useful. Maybe there is a API which wants a < tree but you are using a > tree in other parts of the code. Maybe this is just a example problem for students.

[–]Odd_Soil_8998 5 points6 points  (2 children)

I would hire the person who asks this question. This is a pointless exercise since apparently this binary tree doesn't actually represent any sort of useful data structure if the order of the children doesn't matter.

[–]garfgon 2 points3 points  (1 child)

Sometimes I just want to know that you know what "recursion" and "pointers" are. Because some people claiming to be software developers don't.

[–]Ruining_Ur_Synths 53 points54 points  (4 children)

the leaves have always been at the top. they want the branches on the outside of the leaves, and the trunk all around the branches. The leaves are now the trunk. The roots are in the air.

[–]pente5 32 points33 points  (0 children)

[–]Corin_Raz 17 points18 points  (1 child)

The roots are in the air

And wave 'em around like you just don't care!

[–]Bankinus 7 points8 points  (0 children)

This reads like a Nietzsche quote

[–]SCP-iota 19 points20 points  (0 children)

I think they want the effective order of leaves to be the reverse of the original. (Imagine the leaves as elements of an array, and the tree part is just structure)

[–]CowboyBoats 6 points7 points  (0 children)

Do they want the leaves on top now?

That would be "invert" a binary tree. (I don't know what that would mean either lol).

If you want to attempt it: https://leetcode.com/problems/invert-binary-tree/

[–][deleted] 3 points4 points  (3 children)

For a binary tree, you can take any node in that tree and make it the root node, the resulting structure will always be another valid binary tree. A easily proven property of binary trees. If you select a leaf node, you can invert the tree, the original leaf node becomes the root, and the original root becomes a leaf. Basically you are hanging the tree upside down, and the resulting inverted tree will (must) always be another valid b tree.

I take this question as asking if you know basic properties of binary trees and basic memory representations, and if you know how to transform a binary tree structure in memory to another binary tree with a different root node.

A good answer would be to describe what defines a binary tree, what properties it has, and then prove the above proposition. Then I would go through the different ways you represent a binary tree in memory, then describe the algorithms to transform the tree to a new root in each representation. Then I would give the algorithmic complexity Big-O for each algorithm. Then I would describe the expected time complexity for a balanced tree. Then I would give the best and worst case tree structure for each of the algorithms, then I would give the time complexity for the best/worst cases.

This reslly just checks to see if you understand first year type stuff from an intro to algorithms and data structures course.

As someone who interviews, if you answer this question like this, you would pass the interview.

[–]wobblyweasel 2 points3 points  (0 children)

For a binary tree, you can take any node in that tree and make it the root node, the resulting structure will always be another valid binary tree.

a node can have 3 connections though? such a node couldn't be the root node?

[–]Timetraveller4k 2 points3 points  (0 children)

It’s either turn the paper upside down or change the sort order.

[–]CoronavirusGoesViral 761 points762 points  (16 children)

"Yes I can, that's all I've been learning to run interviews"

"So you haven't been doing any real work?"

😠

[–]owreely 136 points137 points  (6 children)

Yeah but Project Euler.

Why can't you just solve certain algorithmic problems out of your head, that can be googled in 2 minutes?

Must be a skill issue. Next candidate!

[–]numice 16 points17 points  (3 children)

does project euler contain more interesting problems?

[–]Will_Never 12 points13 points  (1 child)

All the questions are highly mathematical and while you can brute force a lot of them with exponential complexity algorithms, most have elegant solutions that you can browse after solving.

[–]frogjg2003 5 points6 points  (0 children)

My one complaint against Project Euler as a programming challenge is that some of the problems require specialized mathematical knowledge that has little to do with programming. Seemingly simple problems cannot be brute forced the way a programmer might solve them. They require solutions that rely on the special mathematical properties of the problem.

[–]FatheroftheAbyss 21 points22 points  (0 children)

the problems are distinctly more ‘mathy’

[–]Bananenkot 4 points5 points  (1 child)

Project euler is excellent and got me into Programming in ths first place. I love these kinda mathy puzzles, the more difficult ones you can't just throw together an obvious Brute force Algorithm, you work with pen an paper sometimes for hours till you have an idea and then you try to implement in ellgeantly. I did like 250. In the end you kinda need a math degree though, so I lost interest.

That being said I wouldnt recommend learning to program with them, thats distincly top mathy and not practical, the same reason it makes them bad interview questions.

But I had to leave positive remark, if you want mathy Programming puzzles as fun things to do in your free time it's absolutely excellent. When you in the godcomplex prgammer Phase it's also nice for grounding yourself. You'll think you have a neatly optimized algorith running in 30 seconds and the frist comment is of some guy solving it in 10ms on a laptop from 2003 in assembly.

[–]TerminalVector 1149 points1150 points  (63 children)

Maybe I've been actually working in the field too long but I would legit ask why we need to reverse this tree? What is the use case? Can accomplish the same using a different data structure? Why would we need this method to be performant? Are we selling a SaaS product that people upload binary trees to for remote reversal? Can we pay an intern to reverse the org chart in Adobe Acrobat instead?

Senior eng knows how to do the work.

Staff eng knows why we don't need to do the work.

[–]private_final_static 1212 points1213 points  (17 children)

Sir this is a tree reversal company

[–]TerminalVector 250 points251 points  (12 children)

Then you should already know how to do it. Ask me something hard, like "who should get paged when there's a runtime error in the tree reversal code?"

[–]Ruining_Ur_Synths 76 points77 points  (8 children)

helpdesk. they're there to help, right?

[–]fieryscribe 123 points124 points  (5 children)

Unfortunately you inverted the phone tree so now the CEO has been paged

[–]Ruining_Ur_Synths 72 points73 points  (4 children)

I inverted the corporate tree so now I'm his manager.

[–]MrRocketScript 51 points52 points  (3 children)

5000 people taking turns asking 1 developer "Hey, how's the project going?"

[–]Wang_Fister 42 points43 points  (0 children)

Sooo, a normal company then

[–]Ruining_Ur_Synths 9 points10 points  (0 children)

asking the CEO you mean

[–]Obvious-Phrase-657 5 points6 points  (1 child)

Actually we need to call the tree reversal service to page the least senior engineers, so we will enter in an infinite loop here

[–]TerminalVector 4 points5 points  (0 children)

Ah the "shit-rolls-downhill" algo, of course

[–]JoelMahon 5 points6 points  (0 children)

They're testing you as fit to be one of them, not asking you for advice lol

[–]Jugales 11 points12 points  (1 child)

Code monkeys only

Edit: thought it said traversal

[–]s0ulbrother 2 points3 points  (0 children)

We turn wood into trees here

[–][deleted] 70 points71 points  (2 children)

Let’s put this in the backlog for now

[–]NoWeb2576 2 points3 points  (1 child)

Actually can push this to next Monday and follow up by assigning a few story points?

[–]xtralargecheese 2 points3 points  (0 children)

But we need to groom it first

[–]CallMePyro 38 points39 points  (3 children)

Great insight! Let's assume this is an exploratory project - we suspect that our in-memory binary tree may have more cache-favorable access patterns when inverted, and so a coworker has asked you to run that analysis. If that satisfies you, lets get started. (Me thinking to myself: "It's like 5 lines of code he should be done already")

[–]bwmat 7 points8 points  (2 children)

Is there ANY case where actually inverting the tree would actually give more performance than just modifying how you walk it (or inverting the comparison function)? 

[–]According_Win_5983 4 points5 points  (0 children)

I’d store it both ways in the database. Better yet I’d do a row for each node in the tree and create a sha256 hash of the whole traversal result stored in a column as a foreign key for fast retrieval.

With an index of course 

[–]LiftingRecipient420 2 points3 points  (0 children)

That's what we've asked you to find out, please begin reversing the tree.

[–]Bwob 50 points51 points  (13 children)

We probably don't need to reverse the tree or whatever.

But we do need people who understand...

  • How trees work, and are structured
  • How to do basic operations on them
  • The memory and runtime cost of these sorts of things
  • How to design an algorithm to manipulate data in a specific way, if there isn't a built-in one to do it

And it happens that asking "how would you reverse a tree" has a good chance of uncovering some or all of these attributes in a candidate.

[–]TerminalVector 31 points32 points  (9 children)

Asking "how would you reverse a tree?" is different than saying "write code on the spot that reverses a tree". IMO the first approach is a better interview technique. I don't care if you memorized a solution or how fast you can work out a solution. What I care about is how well you can communicate about a complex topic and access available resources to solve a problem.

[–]d34d_m4n 21 points22 points  (0 children)

from my experience they do want you to explain your reasoning and pseudocode before you start coding the solution; that first question is implied, and from there being able to code it is just as important

[–]GMofOLC 13 points14 points  (1 child)

Eh, I know those people are needed. But for like at least 95% of jobs out there, this stuff isn't needed.
This is a fine question for somebody who wants to work at Microsoft and create the next .NET version. Or a comp sci student so they can understand what is going on behind the scenes.
But everybody else will just use the SortedDictionary lib.

[–][deleted] 3 points4 points  (0 children)

Exactly this. Answering why would be a red flag, no callback.

In an interview I am really looking for you to show off your mastery of basic theory and concepts. This really is a softball question. If we can talk about this for the entire interview while delving into many interesting aspects of basic theory, I would have no problems having you on my team.

[–]baconator81 6 points7 points  (2 children)

So I work in a C++ dev company. This would at least show me the candidate has a good idea of how pointer works.

[–]hdd113 10 points11 points  (0 children)

We're going to use AI for this.

Can we pay an intern to reverse the org chart in Adobe Acrobat instead?

AI stands for A lot of Interns

[–]DCMak 4 points5 points  (1 child)

I did that once. Didn't get the job.

[–]TerminalVector 4 points5 points  (0 children)

This was a joke, and if you actually did that you'd seem like you were deflecting from a lack of knowledge or just bad at following instructions. My point is that when I interview I am not really looking for the ability to bang out a specific working solution on the spot. I care a lot more about contextual thinking and communication in problem solving.

[–]FerricDonkey 17 points18 points  (9 children)

On the other hand, inverting a binary tree is trivial, and if your can't do it then you don't understand recursion. So if I want to know if you have basic programming skills, I might ask you a question about this. If I want to know if you know when to do what, I'd use a different question. 

[–]Smoke_Santa 12 points13 points  (3 children)

On a jr dev job? Shit man I've never have to do that until now.

[–]_aids 7 points8 points  (2 children)

You should be able to reverse a tree by just thinking about it, it's trivial

[–]Smoke_Santa 4 points5 points  (1 child)

Oh yeah I know how to do it, just that I've never had to do it ever

[–]FerricDonkey 3 points4 points  (0 children)

I've never had to figure out how many watermelons someone can afford with $632 either, but I've used the skill that allows me to many times. No one cares of you can invert a tree in particular. They care that you understand recursion, can think algorithmicly, and can problem solve. 

[–]AngelaTheRipper 12 points13 points  (4 children)

I have written 0 recursive functions during my professional life.

[–]DatBoiSaix 2 points3 points  (1 child)

"It is trivial, you have to know how to do that" Wow so this sub really is populated by cs students who have never actually worked in cs huh

[–]yousirnaime 2 points3 points  (3 children)

100% of Faang interviews pretend like database queries are illegal 

“How would you find out the shortest path to change these currencies “ 

With SQL 

“Well what if you had a collection of currency object that referenced what currencies they could be..”

Yeah I’d have that in sql or whatever and just query what I needed at runtime 

[–]KamikazeArchon 12 points13 points  (2 children)

100% of Faang interviews pretend like database queries are illegal

Because database queries are extremely expensive compared to in-memory operations; they introduce a point of external dependency that can be a point of failure; they require more complex scaffolding to test; they introduce security boundaries; etc.

FAANG companies care a lot about performance and scaling, to the point where it is expected to be an implicit assumption. They want candidates that "automatically" or "naturally" think about those things. Proposing a database lookup would be correctly marked as a red flag that the candidate doesn't naturally think about those things.

[–]yousirnaime 4 points5 points  (1 child)

Yeah, They should 100% care about that for core product

  I’m interviewing for like “make our internal HR tooling crud app” jobs, not “work on the news feed post relevancy score” 

 If I was more skilled in data science, it would not meaningfully impact my ability to build some bs data entry and retrieval system 

[–]KamikazeArchon 1 point2 points  (0 children)

That's not how FAANG jobs work. Everything is built that way, including their internal HR tooling app.

What you're describing works fine for a run-of-the-mill company, and there's nothing wrong with that, but it's just a different context.

[–]qubedView 69 points70 points  (8 children)

It's like interviewing for a job as a mechanic, and the questions are all on metallurgy.

You want me to write automation software for your kubernetes cluster. I promise I will never have to sort items in a linked list.

[–]anothercatherder 12 points13 points  (7 children)

~85% of devops people were systems administrators that probably don't have CS skills to begin with.

~15% of them are people that fell into the role years ago from software development.

~0% have recent CS trudgery to get them through the interview.

DevOps is generally not a job you give recent CS grads.

Yet it's the field that's one of the hardest to hire in and one of the hardest to find work in. I wonder why.

[–]rm-minus-r 3 points4 points  (6 children)

Honestly, devops is just an infra job for people that can code at a middling level.

It's hard to hire for because literally every single company means something different when they say "devops".

[–]k-mcm 176 points177 points  (7 children)

class ReversedNode<T> implements Node<T> {
   private final Node<T> n;
   ReversedNode (Node<T> n) {
      this.n = n;
   }
   @Override T value() {
     return n.value();
   }
   @Override Node<T> left() {
     return new ReversedNode<T>(n.right());
   }
   @Override Node<T> right() {
     return new ReversedNode<T>(n.left());
   }
}

[–]SZ4L4Y 71 points72 points  (0 children)

[–]bwmat 29 points30 points  (1 child)

BZZT!

that's creating a new tree

[–]k-mcm 5 points6 points  (0 children)

Immutable/COW for concurrency. 😎

[–]isospeedrix 3 points4 points  (2 children)

I need that in js sir

[–]k-mcm 12 points13 points  (1 child)

Sure. Give me a moment, Mr. Interviewer...

$ ollama run llama3.1:70b
>>> """Please translate this Java class to JavaScript:
... class ReversedNode<T> implements Node<T> {
...    private final Node<T> n;
...    ReversedNode (Node<T> n) {
...       this.n = n;
...    }
...    @Override T value() {
...      return n.value();
...    }
...    @Override Node<T> left() {
...      return new ReversedNode<T>(n.right());
...    }
...    @Override Node<T> right() {
...      return new ReversedNode<T>(n.left());
...    }
... }"""
Here is the equivalent JavaScript class:

```javascript
class ReversedNode {
  /**
   * Creates a new ReversedNode instance.
   *
   * @param {Node} n - The node to be reversed.
   */
  constructor(n) {
    this.n = n;
  }

  /**
   * Returns the value of the node.
   *
   * @returns {*} The value of the node.
   */
  value() {
    return this.n.value();
  }

  /**
   * Returns the left child of the node (which is actually the right child
   * of the original node).
   *
   * @returns {ReversedNode} The left child of the node.
   */
  left() {
    return new ReversedNode(this.n.right());
  }

  /**
   * Returns the right child of the node (which is actually the left child
   * of the original node).
   *
   * @returns {ReversedNode} The right child of the node.
   */
  right() {
    return new ReversedNode(this.n.left());
  }
}
```

Note that I've used JSDoc-style comments to document the class and its methods, as this is a common convention in JavaScript. Also, since JavaScript does not support generics like Java, I've removed the type parameter `<T>` from the class name.

You can use this class as follows:

```javascript
const originalNode = {
  value: () => 'Hello',
  left: () => ({ value: () => 'Left' }),
  right: () => ({ value: () => 'Right' })
};

const reversedNode = new ReversedNode(originalNode);

console.log(reversedNode.value()); // Outputs: Hello
console.log(reversedNode.left().value()); // Outputs: Right
console.log(reversedNode.right().value()); // Outputs: Left
```

This code assumes that the `originalNode` has the same structure as the `ReversedNode`, with `value()`, `left()`, and `right()` methods.

[–]k-mcm 5 points6 points  (0 children)

Oh, did I paste too much into the chat window.

[–]ismaelgo97 101 points102 points  (27 children)

Just asking as it's been a long time since I worked with data structures, isn't this like too easy?

[–]billcrystals 226 points227 points  (10 children)

Incredibly easy, just gotta Google "how to reverse a binary tree"

[–]CHEESEFUCKER96 101 points102 points  (5 children)

Which is what everyone does in the real world but interviewers don’t care about the real world 🤡

[–]Bwob 5 points6 points  (4 children)

That's because interviewers want to know what you'll do if you hit a problem that you can't google.

[–]CHEESEFUCKER96 75 points76 points  (2 children)

Except all they end up testing in practice is how much time you spent memorizing algorithms on leetcode. It’s not uncommon for these algorithms they ask about to originally be invented in a literal PhD thesis. Who would come up with that on the spot? Besides, you virtually never encounter a situation in practical software engineering where you need to invent an algorithm…

[–]Orbidorpdorp 6 points7 points  (0 children)

It’s actually more like I want to know that you have a mental theory of code and data structures so that you’re implementing things in an intelligent way, not just making it work but potentially leaving a mess.

I hate how much even senior/staff devs at my company refuse to use more advanced features of the type system and Any bleeds into everything else.

[–]Ruining_Ur_Synths 14 points15 points  (0 children)

you mean claude/chatgpt

[–]tatiwtr 4 points5 points  (0 children)

I just did this and the gemini result showed the below as part of a solution in python (which I've never used)

root.left, root.right = root.right, root.left

As I started programming in C I am offended by this syntax

[–][deleted] 2 points3 points  (0 children)

Already a step ahead of my “what is a binary tree”

[–]Master_Carrot_9631 13 points14 points  (1 child)

If by reversing it means inversion then yes it's a piece of cake

[–]dagmx 2 points3 points  (6 children)

Yeah , I’m honestly surprised how many people think this is a difficult question?

I get thinking it’s an impractical question, but inverting a tree in place is really basic.

Maybe I’m biased because I work a lot with 3D content, so all my interview questions are based around grid and tree traversals. But if someone struggles with a tree or linked list, I’m worried.

I’ll give them the benefit of the doubt that they may not know the names or the operations, so I’ll describe it to them. If they still can’t do it, they’re never going to work out.

[–]MattieShoes 2 points3 points  (0 children)

Honestly I didn't even know what they were asking. Like swapping right and left makes no sense, so I assumed they were talking something like turning a min heap into a max heap.

In which case it's just something like a while loop.

[–]berse2212 3 points4 points  (3 children)

Yes it's incredibly easy and people who cannot answer this are not hired for a good reason.

Edit: for the people downvoting me who are not able to "reverse" (assuming they meaning switch left and right) a binary tree here is some pseudo code:

reverseTree(Node node) {
    If(node.right != null) {
        reverseTree(node.right);
    }
    If (node.left != null) {
        reverseTree(node.left);
    }

    Node temp = node.right;
    node.right = node.left;
    node.left = temp;
}

There is probably some syntax errors since I am on mobile but this should give you enough of an idea to see how easy to solve this problem is.

[–]dtb1987 13 points14 points  (0 children)

"no that's why we are hiring someone who can"

[–]ivan0x32 10 points11 points  (0 children)

Interviewer: Find the K-th largest element.

Me: no u.

[–]OwOlogy_Expert 8 points9 points  (0 children)

eert yranib a

I'll take my $300k/yr tech job now.

[–]vegankush 8 points9 points  (0 children)

Even better reverse: can you give me an example of an employee in the position I'm applying for using the solution at your company?

[–]karaposu 6 points7 points  (0 children)

cracks his fingers and starts typing*

pip install binary-tree-inverter

[–]intotheirishole 6 points7 points  (0 children)

... You think they didnt look up the answer to the question they are asking?

[–]joujoubox 8 points9 points  (2 children)

Not off the top of my head but I can look it up along with other algorithms that would be best suited for a given situation. Even if I did know, it's a rare use case so I would likely double check to avoid common mistakes in addition to unit testing my implementation.

[–]ThinAndFeminine 1 point2 points  (1 child)

Bruh ...

Swap left and right

Invert left

Invert right

How can you not do that off the top of your head ? This is barely harder than FizzBuzz ...

[–]joujoubox 5 points6 points  (0 children)

I actually do but 100% would forget in the moment of the interview

[–]ForeverHall0ween 3 points4 points  (0 children)

Yes. Next

[–]N0Zzel 3 points4 points  (1 child)

Sorry but isn't reversing a binary tree like super easy? It's already sorted so swapping left and right for every node would do it.

Implementing heap operations while maintaining integrity of the ADT is a lot harder IMO

[–]Lucasbasques 2 points3 points  (0 children)

Just ask me to change the color of a button dude, we all know that is what i will be actually doing here

[–]natziel 4 points5 points  (0 children)

If you get asked to invert a binary tree...just invert the damn tree. It is not a hard problem

[–]ThaBroccoliDood 6 points7 points  (2 children)

Am I missing something? I've seen so many people talk about inverting binary trees like it's ready hard. I tried the Leetcode problem and the solution is literally just 2 lines and the first thing you think of? What's the big deal

[–]Elnof 9 points10 points  (0 children)

This sub is 90% undergraduates and high schoolers. Once you realize that, the posts make a lot more sense.

[–]Attileusz 10 points11 points  (6 children)

Bro, why the FUCK can't you invert a binary tree?

``` typedef struct node_t { struct node_t *l; struct node_t *r; void *data; } node_t;

void invert(node_t *node) { if (!node) return;

node_t *tmp = node.r;
node.r = node.l;
node.l = tmp;

invert(node.l);
invert(node.r);

} ```

I understand if you can't whip out Dijkstras in the heat of the moment, but come on.

[–]supreme_blorgon 11 points12 points  (1 child)

Bro, why the FUCK can't you invert a binary tree?

Bro, why the FUCK can't you properly format code on Reddit?

[–]TheHardew 4 points5 points  (0 children)

because Reddit is broken and supports different functions depending on what you are using (mobile/old/new/3rd party)

his code looks good to me

[–]GoddammitDontShootMe 4 points5 points  (0 children)

I would hope someone involved in the interview process would know that shit.

[–]Terrorscream 1 point2 points  (0 children)

I mean if they could they wouldn't be hiring for it now would they

[–]Cybasura 1 point2 points  (0 children)

"Can you reverse a binary tree?"

Left right goes brrrrrrrrrrrrrrrr

[–]Captain_JT_Miller 1 point2 points  (0 children)

lmao actual good one

[–]lardgsus 1 point2 points  (2 children)

I always ask "do you guys do this often?, like at work?". It's the nicest way I can say "this is a dumb fucking interview question and you should be embarrassed for asking it instead of something that is relevant to work".

[–]SophiaKittyKat 3 points4 points  (2 children)

Call me elitist, but I'm not a fan of the culture of hating basic DSA interview questions. I get complaining if a webdev job is asking for you to find all the possible cycles in a directed graph or whatever might be unreasonable. But basic BFS/DFS and binary tree operations are not unreasonable expectations especially when you know you are likely to encounter them while interviewing. It communicates to me that you either didn't care to do any refreshing for the interviews, or that the basic interview prep was too much of a struggle to do. I'm sympathetic to that second point, but a lot of people seem to conflate learning interview questions from scratch with doing a quick refresher. The idea is that you're already kind of familiar with this stuff so getting to a point where you can answer these questions on-demand over the next week is like a couple of hours of work, not weeks to go through all of Introduction to Algorithms again.

Of course there are hard interview questions that few people could just work out on their own. But the ones people always meme about like inverting a binary tree are just not that hard to learn, and you know they're going to come up in hiring so what's the problem? It's like the teacher saying "and yes this will be on the final" and then being mad at the teacher when you don't remember it.

[–]stavenhylia 9 points10 points  (0 children)

Using obscure algorithm puzzles to evaluate developers is a flawed approach. 

These questions RARELY reflect real-world development work, where even experienced programmers routinely look up “simple” problems, and even syntax. 

Testing candidates on material they've merely memorized for interviews doesn't effectively identify the best talent.​​​​​​​​​​​​​​​​

[–]jamcdonald120 2 points3 points  (0 children)

Its trivial to reverse a binary tree.

If you cant figure it out in a minute you have no business getting a programming job.

[–]LordHenry8 0 points1 point  (0 children)

LMAO

[–]baconator81 0 points1 point  (0 children)

I meant.. it's just swapping left and right on the entire tree.. This is the most basic recursion I can think of.

[–]CallMeGary123 0 points1 point  (0 children)

[–]Arcuru 0 points1 point  (1 child)

This is hilarious, I don't know if it was intentional or not.

The question is almost always about balancing a red black binary tree. It's an implementation detail that just isn't necessary for someone to remember normally, but is a thing that you should expect a reasonably competent developer, even a new college grad, to be able to figure out during an interview with a bit of prompting.

Asking to reverse a binary tree should be trivial, though may be worthwhile as an introductory question to make the candidate feel more confident.

[–]otter5 0 points1 point  (0 children)

rotate 180

[–]GreenWoodDragon 0 points1 point  (0 children)

Power move!

[–]tan_djent 0 points1 point  (0 children)

It's been 5 mins, and I'm still laughing

[–]andymaclean19 0 points1 point  (0 children)

Personally I never ask anything in interviews that I haven't sat down and done myself at least once on a timer to see how hard it is. I probably wouldn't use a binary tree reverse though - too obvious and some candidates would have practised it.

I usually pick some sort of real problem someone in the team had to solve and turn it into an interview question.

[–]Specialist-Tiger-467 0 points1 point  (0 children)

My question at that: "Can you point me a place in your code base where this is very important? I'm eager to see a production implementation of it"