4 ms·

In this case, it means to reverse the binary tree, so that you get the largest item by iterating down the left branch to the bottom of the tree. You would do th

In this case, it means to reverse the binary tree, so that you get the largest item by iterating down the left branch to the bottom of the tree. You would do this by breadth-first scanning the tree, swapping the left and right pointers as you go.

attilaolah 11y ago
Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf. If this was really about "reversing" the tree, as you mention, the question seems more likely to address how the candidate approaches the situation. Like, he should start by making sure they both agree on what the question actually means. Once that's out of the way, it seems relatively easy to come up with a naive solution, without having memorised any algorithms. It seems more like a case of brainfreeze to me, which can be sort-of fixed with practice (which in turn many candidates refuse to do: the dreaded "If I have to cram for the interview, I don't want the job" statement.) So maybe he really wasn't a good fit for Google, despite apparently being a rockstar developer. Hey, startups need rockstar devs too.
- DannoHung 11y ago
  I was gonna say, who calls reversing a tree's ordering inverting? > Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf. Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link?
  - morpher 11y ago
    >I was gonna say, who calls reversing a tree's ordering inverting? The guy writing the tweet (not necessarily the interviewer).
  - attilaolah 11y ago
    > Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link? https://wwwx.cs.unc.edu/~duozhao/entry/2014/12/binary-tree-upside-down/ https://wwwx.cs.unc.edu/~duozhao/entry/2014/12/binary-tree-u...
im3w1l 11y ago
Depth-first would consume less memory for balanced trees.

attilaolah 11y ago

Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf. If this was really about "reversing" the tree, as you mention, the question seems more likely to address how the candidate approaches the situation. Like, he should start by making sure they both agree on what the question actually means. Once that's out of the way, it seems relatively easy to come up with a naive solution, without having memorised any algorithms. It seems more like a case of brainfreeze to me, which can be sort-of fixed with practice (which in turn many candidates refuse to do: the dreaded "If I have to cram for the interview, I don't want the job" statement.) So maybe he really wasn't a good fit for Google, despite apparently being a rockstar developer. Hey, startups need rockstar devs too.

DannoHung 11y ago
I was gonna say, who calls reversing a tree's ordering inverting? > Oddly enough, Google shows me interview questions where "inverting a binary tree" means something quite different — for example, flipping it upside down, and making the left leaf the root, the right leaf the left leaf and the root the right leaf. Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link?
- morpher 11y ago
  >I was gonna say, who calls reversing a tree's ordering inverting? The guy writing the tweet (not necessarily the interviewer).
- attilaolah 11y ago
  > Whaaaaa? I can't find this, but it seems like such a weird operation. Got a link? https://wwwx.cs.unc.edu/~duozhao/entry/2014/12/binary-tree-upside-down/ https://wwwx.cs.unc.edu/~duozhao/entry/2014/12/binary-tree-u...

im3w1l 11y ago

Depth-first would consume less memory for balanced trees.