/**
 *	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.
 *
 *	Author: matao
 *
 */

class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) { val = x; }
}

public class InvertBinaryTree {
	public static TreeNode invertTree(TreeNode root) {
		if (root == null) {
			return null;
		}
		TreeNode tmp = root.left;
		root.left = root.right;
		root.right = tmp;

		root.left = invertTree(root.left);
		root.right = invertTree(root.right);

		return root;
    }

    public static void traversePreOrder(TreeNode root) {
    	if(root == null) {
    		return;
    	}
    	System.out.print(root.val + " ");
    	traversePreOrder(root.left);
    	traversePreOrder(root.right);
    }

	public static void main(String[] args) {
		TreeNode node4 = new TreeNode(4);		
		TreeNode node2 = new TreeNode(2);		
		TreeNode node7 = new TreeNode(7);		
		TreeNode node1 = new TreeNode(1);		
		TreeNode node3 = new TreeNode(3);		
		TreeNode node6 = new TreeNode(6);		
		TreeNode node9 = new TreeNode(9);		

		node4.left = node2;
		node4.right = node7;

		node2.left = node1;
		node2.right = node3;

		node7.left = node6;
		node7.right = node9;

		traversePreOrder(node4);

		System.out.println();

		traversePreOrder(invertTree(node4));
	}
}
@@ -418,16 +418,41 @@
  *%0A */%0A%0A
+import java.util.Stack;%0A%0A
 class Tr
@@ -602,16 +602,17 @@
 vertTree
+1
 (TreeNod
@@ -758,24 +758,25 @@
 = invertTree
+1
 (root.left);
@@ -801,16 +801,17 @@
 vertTree
+1
 (root.ri
@@ -839,16 +839,487 @@
 %0A    %7D%0A%0A
+    // non-recursive%0A    public static TreeNode invertTree2(TreeNode root) %7B%0A%09%09if (root == null) %7B%0A%09%09%09return null;%0A%09%09%7D%0A%09%09Stack%3CTreeNode%3E stack = new Stack%3CTreeNode%3E();%0A%09%09stack.push(root);%0A%09%09while(!stack.isEmpty()) %7B%0A%09%09%09TreeNode node = stack.pop();%0A%09%09%09TreeNode tmp = node.left;%0A%09%09%09node.left = node.right;%0A%09%09%09node.right = tmp;%0A%09%09%09if(node.left != null) %7B%0A%09%09%09%09stack.push(node.left);%0A%09%09%09%7D%0A%09%09%09if(node.right != null) %7B%0A%09%09%09%09stack.push(node.right);%0A%09%09%09%7D%0A%09%09%7D%0A%09%09return root;%0A    %7D%0A%0A
     publ
@@ -2056,16 +2056,17 @@
 vertTree
+2
 (node4))

add non-recursive solution