Amazon

Microsoft

VMware

2020-06-01

## 226. Invert Binary Tree

### Question:

Invert a binary tree.

#### Example 1:

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

#### Example 2:

``````     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 f*** off.

### Solution:

Using DFS to traverse the tree (Preorder traversal).

``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode() {}
*     TreeNode(int val) { this.val = val; }
*     TreeNode(int val, TreeNode left, TreeNode right) {
*         this.val = val;
*         this.left = left;
*         this.right = right;
*     }
* }
*/
class Solution {
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;
}
}
``````