Invert binary tree

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.

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 queue = new LinkedList<>();
    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;
}

References

• LeetCode – 226. Invert Binary Tree

Have fun ~