Invert Binary Tree

Problem

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9
to
     4
   /   \
  7     2
 / \   / \
9   6 3   1

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 fuck off.

Solution

Recursive solution with time O(n) and space O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) return null;
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;
    }
}

Concise version of above solution

public class Solution {
  public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tempLeft = invertTree(root.left);
    root.left = invertTree(root.right);
    root.right = tempLeft;
    return root;
  }
}

Iterative BFS solution

public class Solution {
  public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    while (!q.isEmpty()) {
      TreeNode node = q.poll();
      //swap 
      TreeNode tempLeft = node.left;
      node.left = node.right;
      node.right = tempLeft;
      if (node.left != null) q.add(node.left);
      if (node.right != null) q.add(node.right);
    }
    return root;
  }
}

Analysis

This is a classic tree problem best-suited for a recursive approach
Everything before the swap in the method won't invert tree, it is only to get to the correct position
Then we have two nodes from two corresponding positions left and right
Then we do swap and simply return the root
In the concise version, we only have one var as tempLeft
We swap in place and set root.right = tempLeft at the end (not invertTree(tempLeft))
Complexity Analysis

• Time: O(n), where n is the number of nodes in the tree. We cannot do better than that, because at the very least we have to visit each node to invert it.
• Space: O(n). The functions will be called in h (height of tree) times on the stack (h == n in skewed tree).

For the iterative solution, it's a manner similar to BFS
We add the root to queue and then swap its children
Then we add non-null children nodes to our queue and continue to swap
At the end, the queue will be empty and every node should be inverted
Complexity Analysis

• Time: O(n), same reason as above
• Space: O(n), n is the leaf level of nodes in the given binary tree