Comment by gizmo

8 years ago

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

5 comments

gizmo

Reply
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.

  • 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.)

      2 replies →