Comment by ezekg

8 years 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.

4 comments

ezekg

Reply
vkou  8 years 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  8 years 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  8 years 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.

      1 reply →