6 ms·

Was it ever figured out what "invert a binary tree" means? At least I had never heard this term used prior to this incident. This has me slightly worried about

by znfii 9y ago

Was it ever figured out what "invert a binary tree" means? At least I had never heard this term used prior to this incident. This has me slightly worried about this particular example somehow, and I'm not quite sure what to make of it...

gizmo 9y ago
It means to swap the left and right arm of each node. So you effectively "mirror" the tree.
- ezekg 9y ago
  Yeah, it's relatively simple once you come to that realization: TreeNode* invertTree(TreeNode* root) { if (root == NULL) { return NULL; } TreeNode* tmp = invertTree(root->left); root->left = invertTree(root->right); root->right = tmp; return root; } It sounds a lot more complicated than it is.
  - vkou 9y ago
    Until I throw this test case at you: TreeNode testRoot = new TreeNode(); testRoot.left = testRoot; invertTree(root); // Stack overflow. But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.
    - archagon 9y ago
      That ought to be done in a separate validation step, and/or the tree object should enforce its invariants. (I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)
      - vkou 9y ago
        I argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a properly formatted integer gracefully. Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.
        archagon 9y ago
        Sure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.
Posibyte 9y ago
I assumed it as taking a binary tree (L|R) and reproducing a tree that's (R|L). And if it is that, then writing out the algorithm on a back of a napkin just now was a pretty thought provoking exercise :)
matthewaveryusa 9y ago
Invert a binary tree as in heapify it maybe because inserting occurs at the leaf not root? Is that what it means? Does it simply mean changing the insert criteria so that a<b is now b<a?
guessmyname 9y ago
2 2 / \ / \ / \ / \ / \ / \ 1 3 3 1 / \ / \ / \ / \ 0 7 9 1 reverse >>> 1 9 7 0 / / \ / \ / \ / \ \ 2 1 0 8 8 8 8 0 1 2 / \ 7 7 — https://leetcode.com/problems/invert-binary-tree/description/ https://leetcode.com/problems/invert-binary-tree/description...
- znfii 9y ago
  So several people replied with this same thing, which I have heard before being suggested. However, as I recall it at the time, if you tried to search for "invert binary tree" this term basically did not exist on the internet. I just tried searching on google with time set between 2000 and end of 2014 which seems to give similar results. I guess I did not spell it out in my original post, but I always felt it might have been an intentional nonsense question intended to gauge how he would react to someone talking nonsense, or something like that, and not necessarily related to technical things. A sibling post of my original to suggest this was the case, without the weird detour through the term "invert binary tree". Edit: Of course an alternative explanation is that the interview used another term and he then used the term "invert" on twitter. Idk, this example at least has to me always felt like people who complain about not passing the driver's test coz they did some minor error and then forgetting to mention that they drove past a stop sign.
  - xiphias 9y ago
    I'm not 100% sure about the inverting part, but at Google nobody ever told me to ,,fuck off'' and nobody would tolerate that language, and that person would get a serious talk from his/her manager, maybe even laid off instantly, especially if it's written.

by znfii 9y ago

gizmo 9y ago

It means to swap the left and right arm of each node. So you effectively "mirror" the tree.

ezekg 9y ago
Yeah, it's relatively simple once you come to that realization: TreeNode* invertTree(TreeNode* root) { if (root == NULL) { return NULL; } TreeNode* tmp = invertTree(root->left); root->left = invertTree(root->right); root->right = tmp; return root; } It sounds a lot more complicated than it is.
- vkou 9y ago
  Until I throw this test case at you: TreeNode testRoot = new TreeNode(); testRoot.left = testRoot; invertTree(root); // Stack overflow. But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.
  - archagon 9y ago
    That ought to be done in a separate validation step, and/or the tree object should enforce its invariants. (I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)
    - vkou 9y ago
      I argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a properly formatted integer gracefully. Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.
      - archagon 9y ago
        Sure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.

Posibyte 9y ago

I assumed it as taking a binary tree (L|R) and reproducing a tree that's (R|L). And if it is that, then writing out the algorithm on a back of a napkin just now was a pretty thought provoking exercise :)

matthewaveryusa 9y ago

Invert a binary tree as in heapify it maybe because inserting occurs at the leaf not root? Is that what it means? Does it simply mean changing the insert criteria so that a<b is now b<a?

guessmyname 9y ago

2 2 / \ / \ / \ / \ / \ / \ 1 3 3 1 / \ / \ / \ / \ 0 7 9 1 reverse >>> 1 9 7 0 / / \ / \ / \ / \ \ 2 1 0 8 8 8 8 0 1 2 / \ 7 7 — https://leetcode.com/problems/invert-binary-tree/description/ https://leetcode.com/problems/invert-binary-tree/description...

znfii 9y ago
So several people replied with this same thing, which I have heard before being suggested. However, as I recall it at the time, if you tried to search for "invert binary tree" this term basically did not exist on the internet. I just tried searching on google with time set between 2000 and end of 2014 which seems to give similar results. I guess I did not spell it out in my original post, but I always felt it might have been an intentional nonsense question intended to gauge how he would react to someone talking nonsense, or something like that, and not necessarily related to technical things. A sibling post of my original to suggest this was the case, without the weird detour through the term "invert binary tree". Edit: Of course an alternative explanation is that the interview used another term and he then used the term "invert" on twitter. Idk, this example at least has to me always felt like people who complain about not passing the driver's test coz they did some minor error and then forgetting to mention that they drove past a stop sign.
- xiphias 9y ago
  I'm not 100% sure about the inverting part, but at Google nobody ever told me to ,,fuck off'' and nobody would tolerate that language, and that person would get a serious talk from his/her manager, maybe even laid off instantly, especially if it's written.