# Invert binary tree

0
1558

Today’s practice algorithm question is to invert a binary tree. This is a very good problem to start learning with tree data structure; specifically, binary tree.

Article Contents

### Problem

Given a binary tree, invert it.

Example:

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

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

### Analysis

Through observation, we can see that the inversion is done by swapping between left nodes and right nodes. So we can apply:

• DFS with pre-order traversal, which is to swap left and right nodes then return parent node.
• BFS with level-order traversal using a queue, for each node in a level, we swap its left child and right child; then, adding children to queue to be processed in next level.

### Solution

The code is written in Java.

#### Using DFS

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

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

root.left = right;
root.right = left;

return root;
}``````

#### Using BFS

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

queue.offer(root);

while (!queue.isEmpty()) {
TreeNode node = queue.poll();
TreeNode left = node.left;
node.left = node.right;
node.right = left;

if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}

return root;
}``````