5 ms·

Since it mentions the infamous interview challenge, I'll ask: has anyone ever "inverted" (i.e. swapped left and right recursively) a binary tree in production

Since it mentions the infamous interview challenge, I'll ask: has anyone ever "inverted" (i.e. swapped left and right recursively) a binary tree in production code? I can't think of any reason why anyone would ever do this. Just navigate the tree in the reverse of your normal direction instead. Why not ask the much more interesting and potentially useful question of balancing a binary tree? Or do something else recursive, if that's what you're after.

sophonX 4y ago
You are just ignorant. You should read about distributed systems. Google around for Zookeeper and it's zab paper. Every (recently with raft protocol) multi master distributed system out there interacts with Zookeeper for assigning leader and maintain configuration. Do you know how the syntax or api calls look like ? They are node path in a tree. You want to store something ? That's a tree path again. You want to listen to some change ? It's tree path again. As I said, most people are ignorant here and don't do "true" computer science engineering in daily life. Most devs simply convert business logic into bunch of apis + adhoc implementation. Did you ever work at a banking firm ? I've read their codebase - they are structured as trees, every damn thing is tree. It's a headache to navigate, code, heck even the objects are literal trees. As I said, people are ignorant and think world revolves around them.
jmd42 4y ago
> Why not ask the much more interesting and potentially useful question of balancing a binary tree? Honestly? Because that's harder. The swapping question is basically a softball / FizzBuzz-style question to test the most basic familiarity with data structures, pointers/references, and recursion.
regularjack 4y ago
> Why not ask the much more interesting and potentially useful question of balancing a binary tree? Or even just when would you use a binary tree? Figuring out which data structure is appropriate for the problem at hand is the hard part, how to implement operations on the data structure is easy in comparison, you can just Google it.
- VonGallifrey 4y ago
  > Or even just when would you use a binary tree? That seems to be the wrong question though. It seems to be jeopardy style "question". You are not asking which data structure is appropriate for a problem. Here is the answer, but what is the problem it solves. Never in my live have I sat down and said: I don't know what problem is I need to solve, but I know the solution is a binary tree.
pessimizer 4y ago
Easier? You usually aren't coding FizzBuzz in production code either (although probably more often than inverting binary trees.)
- snozolli 4y ago
  Easier? What's easier? You usually aren't coding FizzBuzz in production code either I would say you're constantly coding FizzBuzz. Looping, modulus arithmetic, and conditionals are all over the code I've written. At least with FizzBuzz you have a test of a person's ability to understand a task, break it down, and make sure the logic is consistent. With tree "inversion" it's not even a sensical request, it's utterly useless, and there are countless more interesting and practical ways to test understanding of recursion and trees. Knowledge that, I would bet, isn't even relevant for 90% of programmers, and if tree traversal were relevant then you'd probably want to jump to way more difficult questions (I'm thinking of the Facebook graph, for example). I agree with the other commenter that it would make far more sense to ask questions like "you need to process data of this type, what provided data structure (e.g. C++'s STL) would you choose?"
  - zeroonetwothree 4y ago
    I've certainly done tree traversal far more than modular arithmetic (at least at work, for fun I do recreational math problems...)
nvarsj 4y ago
It's not really the point of the question. The LC interview is basically a standardized test to eliminate bias as much as possible. If you prepare, you should be able to solve it. "Invert a binary tree" is actually considered an easy problem to test your basic knowledge of how trees work and tree traversal.
- snozolli 4y ago
  a standardized test to eliminate bias as much as possible Uhhhh... It eliminates competent, skilled people who don't have the time to memorize the latest cargo cult trends in hiring. Look in the article for a glaring example. "Invert a binary tree" is actually considered an easy problem to test your basic knowledge of how trees work and tree traversal. So would simply printing out a tree, and at least that's something a person might actually do. Tree "inversion" doesn't even make any sense and at this point I'm convinced that the cargo cult is choosing it because it's the extent of their own understanding of trees and somehow sounds extra technical to them.
  - sophonX 4y ago
    Why do you want to memorize it ? What happened to thinking logically ? People just complain for everything - they want it to be easy, say it's unfair.
  - jmd42 4y ago
    I think it's more that the "inversion" interview story became a bit of a hot topic, and so is something people tend to reference in these discussions. Not that it's a specific problem people think is great to ask in interviews. It also seems to neatly split people into camps who think "this is trivial, and totally reasonable to expect somebody to answer, even if it's a little contrived", vs those who think "this is not practical, and you'd only know the answer if you'd already practiced it, so it's not fair to ask". > It eliminates competent, skilled people who don't have the time to memorize the latest cargo cult trends in hiring But given that you already acknowledged that it's pretty trivial, why would memorization be necessary for a competant person?
  - nvarsj 4y ago
zeroonetwothree 4y ago
The point is just to ask a simple tree traversal question, to see if you know how to traverse a tree (or more generally, write recursive functions and operate on basic data structures). They could have asked some other operation instead, but this one is one of the easiest so it seems fine.

sophonX 4y ago

You are just ignorant. You should read about distributed systems. Google around for Zookeeper and it's zab paper. Every (recently with raft protocol) multi master distributed system out there interacts with Zookeeper for assigning leader and maintain configuration. Do you know how the syntax or api calls look like ? They are node path in a tree. You want to store something ? That's a tree path again. You want to listen to some change ? It's tree path again. As I said, most people are ignorant here and don't do "true" computer science engineering in daily life. Most devs simply convert business logic into bunch of apis + adhoc implementation. Did you ever work at a banking firm ? I've read their codebase - they are structured as trees, every damn thing is tree. It's a headache to navigate, code, heck even the objects are literal trees. As I said, people are ignorant and think world revolves around them.

jmd42 4y ago

> Why not ask the much more interesting and potentially useful question of balancing a binary tree? Honestly? Because that's harder. The swapping question is basically a softball / FizzBuzz-style question to test the most basic familiarity with data structures, pointers/references, and recursion.

regularjack 4y ago

> Why not ask the much more interesting and potentially useful question of balancing a binary tree? Or even just when would you use a binary tree? Figuring out which data structure is appropriate for the problem at hand is the hard part, how to implement operations on the data structure is easy in comparison, you can just Google it.

VonGallifrey 4y ago
> Or even just when would you use a binary tree? That seems to be the wrong question though. It seems to be jeopardy style "question". You are not asking which data structure is appropriate for a problem. Here is the answer, but what is the problem it solves. Never in my live have I sat down and said: I don't know what problem is I need to solve, but I know the solution is a binary tree.

pessimizer 4y ago

Easier? You usually aren't coding FizzBuzz in production code either (although probably more often than inverting binary trees.)

snozolli 4y ago
Easier? What's easier? You usually aren't coding FizzBuzz in production code either I would say you're constantly coding FizzBuzz. Looping, modulus arithmetic, and conditionals are all over the code I've written. At least with FizzBuzz you have a test of a person's ability to understand a task, break it down, and make sure the logic is consistent. With tree "inversion" it's not even a sensical request, it's utterly useless, and there are countless more interesting and practical ways to test understanding of recursion and trees. Knowledge that, I would bet, isn't even relevant for 90% of programmers, and if tree traversal were relevant then you'd probably want to jump to way more difficult questions (I'm thinking of the Facebook graph, for example). I agree with the other commenter that it would make far more sense to ask questions like "you need to process data of this type, what provided data structure (e.g. C++'s STL) would you choose?"
- zeroonetwothree 4y ago
  I've certainly done tree traversal far more than modular arithmetic (at least at work, for fun I do recreational math problems...)

nvarsj 4y ago

It's not really the point of the question. The LC interview is basically a standardized test to eliminate bias as much as possible. If you prepare, you should be able to solve it. "Invert a binary tree" is actually considered an easy problem to test your basic knowledge of how trees work and tree traversal.

snozolli 4y ago
a standardized test to eliminate bias as much as possible Uhhhh... It eliminates competent, skilled people who don't have the time to memorize the latest cargo cult trends in hiring. Look in the article for a glaring example. "Invert a binary tree" is actually considered an easy problem to test your basic knowledge of how trees work and tree traversal. So would simply printing out a tree, and at least that's something a person might actually do. Tree "inversion" doesn't even make any sense and at this point I'm convinced that the cargo cult is choosing it because it's the extent of their own understanding of trees and somehow sounds extra technical to them.
- sophonX 4y ago
  Why do you want to memorize it ? What happened to thinking logically ? People just complain for everything - they want it to be easy, say it's unfair.
- jmd42 4y ago
  I think it's more that the "inversion" interview story became a bit of a hot topic, and so is something people tend to reference in these discussions. Not that it's a specific problem people think is great to ask in interviews. It also seems to neatly split people into camps who think "this is trivial, and totally reasonable to expect somebody to answer, even if it's a little contrived", vs those who think "this is not practical, and you'd only know the answer if you'd already practiced it, so it's not fair to ask". > It eliminates competent, skilled people who don't have the time to memorize the latest cargo cult trends in hiring But given that you already acknowledged that it's pretty trivial, why would memorization be necessary for a competant person?
- nvarsj 4y ago

zeroonetwothree 4y ago

The point is just to ask a simple tree traversal question, to see if you know how to traverse a tree (or more generally, write recursive functions and operate on basic data structures). They could have asked some other operation instead, but this one is one of the easiest so it seems fine.