Invert a Binary Tree

Given the root of a binary tree, invert it (mirror it left to right) and return the root. Every node's left and right children are swapped.

LeetCode: 226. Invert Binary Tree

Example

Text

      4                 4
    /   \             /   \
   2     7    ->     7     2
  / \   / \         / \   / \
 1   3 6   9       9   6 3   1

Recursive

Swap the root's children, then invert each subtree. A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root. Swapping two children is three assignments through a temporary variable.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static TreeNode invert(TreeNode root) {
        if (root == null) return null;
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        invert(root.left);
        invert(root.right);
        return root;
    }

    static List<Integer> levelOrder(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            values.add(n.val);
            if (n.left != null) queue.add(n.left);
            if (n.right != null) queue.add(n.right);
        }
        return values;
    }

    public static void main(String[] args) {
        TreeNode root = node(4, node(2, leaf(1), leaf(3)), node(7, leaf(6), leaf(9)));
        invert(root);
        System.out.println(levelOrder(root));
        invert(root); // inverting twice restores the original
        System.out.println(levelOrder(root));
        System.out.println(levelOrder(invert(null)) + " " + levelOrder(invert(leaf(5))));
    }
}

Output

[4, 7, 2, 9, 6, 3, 1]
[4, 2, 7, 1, 3, 6, 9]
[] [5]

Time: O(n). Space: O(h) for the recursion: up to O(n) for a skewed tree, which can throw StackOverflowError for very deep trees.

Iterative with an explicit stack

The order in which nodes are inverted does not matter, so any traversal works. An explicit stack of nodes removes the recursion. After swapping a node's children, push both non-null children. ArrayDeque used with push and pop is the standard stack in Java, and it rejects null, so the code checks for null before pushing.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static TreeNode invert(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        if (root != null) stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode n = stack.pop();
            TreeNode tmp = n.left;
            n.left = n.right;
            n.right = tmp;
            if (n.left != null) stack.push(n.left);
            if (n.right != null) stack.push(n.right);
        }
        return root;
    }

    static List<Integer> levelOrder(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if (root != null) queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode n = queue.poll();
            values.add(n.val);
            if (n.left != null) queue.add(n.left);
            if (n.right != null) queue.add(n.right);
        }
        return values;
    }

    public static void main(String[] args) {
        TreeNode root = node(4, node(2, leaf(1), leaf(3)), node(7, leaf(6), leaf(9)));
        invert(root);
        System.out.println(levelOrder(root));
        invert(root);
        System.out.println(levelOrder(root));
        System.out.println(levelOrder(invert(null)) + " " + levelOrder(invert(leaf(5))));
    }
}

Output

[4, 7, 2, 9, 6, 3, 1]
[4, 2, 7, 1, 3, 6, 9]
[] [5]

Time: O(n). Space: O(h): the stack holds at most one waiting sibling per level. It lives on the heap, so a deep tree cannot overflow the call stack.

Edge cases

Empty tree or single node: unchanged.
Inverting twice: gives back the original tree.