Invert a binary tree.

Trivia:
This problem was inspired by this original tweet by Max Howell:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f* off.

Difficulty:Medium

Category:Tree

Solution

Solution 1: Recursive

// Time complexity: O(n), Space complexity: O(h) extra space for the call stack where h is the height of the tree
TreeNode* invertTree(TreeNode* root) {
  if (root == nullptr) return nullptr;
  swap(root->left, root->right);
  invertTree(root->left);
  invertTree(root->right);
  return root;
}

Solution 2: Iterative

Using Queue