On: Inverting Binary Trees Considered Harmful

[discardorama]

> I'll be the contrarian and claim that inverting a binary tree is a perfectly reasonable interview question.

The fact that so many people in the previous discussion could not even tell what that means is a very bad sign.

[blahblah3 → discardorama]

that doesn't mean the interview question was bad, presumably in the actual google interview they defined the problem. people are confused because he didn't define "invert" in the twitter post

[steego → discardorama]

I'm still not entirely sure what that means. Does it mean you recursively swap left and right branches, or does it mean you create a new data structure where the bottom elements become the top elements?

[discardorama → steego]

Apparently it means to swap the left and right subtrees. How's that "inversion"? I'd call it "flipping" or "mirroring" or something... If this is the case, then it's a trivial solution: invert(left_child); invert(right_child);

[59nadir → discardorama]

Or, if the structure is this:

    struct node {
            struct node *left_node;
            struct node *right_node;
            int val;
    };

    struct reversed_node {
            struct reversed_node *right_node;
            struct reversed_node *left_node;
            int val;
    };

No? You then just have a different mapping for the exact same data, no traversal needed.