Problem

Given the root of a binary tree, invert the tree, and return its root.

OR

Change a tree so that the roles of the left and right pointers are swapped at every node.

Example

Example 1 Given binary tree

     1
   /   \
  2     3
 / \   / \
4   5 6   7

invert and return

     1
   /   \
  3     2
 / \   / \
7   6 5   4

root=[1,2,3,4,5,6,7]
output: [1,3,2,7,6,5,4]

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

Solution

The solution is short, but very recursive. As it happens, this can be accomplished without changing the root node pointer, so the return-the-new-root construct is not necessary. Alternately, if you do not want to change the tree nodes, you may construct and return a new mirror tree based on the original tree.

Method 1 - Recursion

Code

Java
public TreeNode invertTree(TreeNode root) {
	if (root != null) {
		dfs(root);
	}

	return root;
}

public void dfs(TreeNode p) {
	TreeNode temp = p.left;
	p.left = p.right;
	p.right = temp;

	if (p.left != null) {
		dfs(p.left);
	}

	if (p.right != null) {
		dfs(p.right);
	}
}

Method 2 - Recursion without Separate Helper Function

Code

Java
public TreeNode invertTree(TreeNode root) {
	if (root == null) {
		return null;
	}

	TreeNode temp = root.left;
	root.left = root.right;
	root.right = temp;

	invertTree(root.left);
	invertTree(root.right);
	return root;
}

Method 3 - Iterative Using Queue and BFS

Here is the iterative solution using BFS(or level order traversal).

Code

Java
public TreeNode invertTree(TreeNode root) {
	LinkedList<TreeNode> queue = new LinkedList<TreeNode> ();

	if (root != null) {
		queue.add(root);
	}

	while (!queue.isEmpty()) {
		TreeNode p = queue.poll();
		if (p.left != null) {
			queue.add(p.left);
		}
		if (p.right != null) {
			queue.add(p.right);
		}

		TreeNode temp = p.left;
		p.left = p.right;
		p.right = temp;
	}

	return root;
}

Method 4 - Iterative Using Stack and DFS

Code

Java
void invertTree(TreeNode tree) {
	if (root==null)
		return;

	Stack<TreeNode> s = new Stack<>();
	s.push(root);
	while (!s.empty()) {
		Node curr = s.pop();

		// Swap the children
		Node temp = current.right;
		current.right = current.left;
		current.left = temp;

		// Push the children on the stack
		if (current.right!=null) {
			s.push(current.right);
		}

		if (current.left!=null) {
			s.push(current.left);
		}
	}
}