A **binary tree** is a *tree* data structure in which each node has at most two children, which are referred to as the left child and the right child. A leaf node is a special node that has only a value. It marks the end of the **tree**. We will also define an empty node that contains no value and no branches.

To invert a binary tree rooted at a node N, Follow this steps.

- Invert its left sub-tree.
- Invert its right sub-tree.
- Change one of its child pointers(say left) to its parent.

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:**

/** * 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 temp = root.left; root.left = invertTree(root.right); root.right = invertTree(temp); return root; } }