☕ DSA Java Articles

Topics › Binary Trees › Medium Problems

Invert/Flip Binary Tree (Create)

Medium TUF ID 2783 Blind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

Given the root of a binary tree, invert it, also called flipping or mirroring: at every node, the left child and the right child trade places. Return the root of the inverted tree. The result is the mirror image of the original, as if the tree were reflected in a vertical line through the root.

There are two common versions, and the “(Create)” in the sheet’s title points at the second:

This article covers both. Constraints: 0 to 100 nodes, values between -100 and 100; the methods are linear and work for any size.

Example 1

input  = [4, 2, 7, 1, 3, 6, 9]          4                4
answer = [4, 7, 2, 9, 6, 3, 1]        /   \            /   \
                                     2     7    ->    7     2
                                    / \   / \        / \   / \
                                   1   3 6   9      9   6 3   1

Example 2

input  = [1, 2]          // 2 is the left child of 1
answer = [1, null, 2]    // after inverting, 2 is the right child

The key observation

Describe a node’s position by the path from the root, a string of L and R moves. In the mirror image every move is reversed: the node at L R L moves to R L R. Swapping the children of one node flips exactly one move, the one taken at that node, for every node below it. So if we swap the children of every node exactly once, each move on every path is flipped exactly once and every node lands at its mirrored position.

Two useful consequences follow. First, the mirror of a tree is “the root, with the mirror of the right subtree on the left and the mirror of the left subtree on the right”, which is a recursive definition. Second, the order in which nodes are swapped does not matter, so any traversal works: depth-first, breadth-first, before or after visiting the children.

Approach 1: Recursion, in place

Intuition. Use the recursive definition directly. Invert the left subtree, invert the right subtree, then attach the inverted right subtree on the left and the inverted left subtree on the right. An empty tree is its own mirror, which is the base case.

Algorithm.

  1. If root is null, return null.
  2. left = recursive(root.left) and right = recursive(root.right).
  3. Set root.left = right and root.right = left, then return root.
static TreeNode recursive(TreeNode root) {
    if (root == null) return null;
    TreeNode left = recursive(root.left);
    TreeNode right = recursive(root.right);
    root.left = right;
    root.right = left;
    return root;
}

Complexity. Time O(n): each node is visited once and does a constant amount of work. Space O(h) for the call stack, where h is the height: O(log n) for a balanced tree, O(n) for a chain.

A classic bug is writing the swap as two lines without saving anything first:

root.left  = invert(root.right);
root.right = invert(root.left);    // root.left was already overwritten on the line above

The second line inverts the subtree that was just placed on the left, so the original left subtree is lost. Storing both results in local variables, as the method does, avoids this.

Approach 2: Iterative breadth-first traversal, in place

Intuition. Because the order of the swaps does not matter, we can visit the nodes level by level with a queue and swap the children of each node as we take it out. No recursion is involved, so a very deep tree cannot overflow the call stack. The Java test inverts a 200,000-node chain this way.

Algorithm.

  1. If root is null, return null. Otherwise put root in a queue.
  2. While the queue is not empty: take a node, swap its left and right, and enqueue whichever children are not null.
  3. Return root.
static TreeNode iterative(TreeNode root) {
    if (root == null) return null;
    Deque<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        TreeNode tmp = node.left;           // swap the children of this node
        node.left = node.right;
        node.right = tmp;
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
    return root;
}

Dry run on Example 1:

node taken children after swap queue after
4 7, 2 7, 2
7 9, 6 2, 9, 6
2 3, 1 9, 6, 3, 1
9, 6, 3, 1 leaves, nothing to swap empty

Reading the tree level by level now gives [4, 7, 2, 9, 6, 3, 1].

Complexity. Time O(n). Space O(w), where w is the largest number of nodes on one level; that is up to about n / 2 for a complete tree. Replacing the queue with a stack gives a depth-first order and O(h) space, with the same result.

Approach 3: Create a new mirrored tree

Intuition. Sometimes the input must not change: other code still holds references to it, or the tree is shared or treated as immutable. Then build a separate tree. For each node, create a copy holding the same value, and build the copy’s left child from the original’s right child (and vice versa). It is the same recursion as Approach 1, except that it allocates new nodes instead of rewiring old ones.

Algorithm.

  1. If root is null, return null.
  2. Create copy with root.val.
  3. copy.left = createMirror(root.right) and copy.right = createMirror(root.left).
  4. Return copy.
static TreeNode createMirror(TreeNode root) {
    if (root == null) return null;
    TreeNode copy = new TreeNode(root.val);
    copy.left = createMirror(root.right);   // the mirror's left side is built from the original's right side
    copy.right = createMirror(root.left);
    return copy;
}

Complexity. Time O(n). Space O(n) for the new nodes plus O(h) for the recursion. The tests check that the input tree is unchanged afterwards and that the mirror shares no node objects with it.

Edge cases and pitfalls