Mirror of a tree

The problem, simply

You get a binary tree: every node has a value, a left child and a right child (either can be empty).

Change it into its mirror image. Whatever was on the left side of any node must end up on the right side, and the other way round, all the way down. Give back the root. This is also called inverting a tree.

A story to remember it

Picture it

Examples

Way 1: the simple way

Build a brand new tree. For each node, make a copy whose left child is the mirror of the old right side, and whose right child is the mirror of the old left side. The old tree is not touched.

1. If the node is empty, the copy is empty.
2. Make a new node with the same value.
3. Its left child is the mirror copy of the old right child.
4. Its right child is the mirror copy of the old left child.

class Solution {
    public TreeNode mirrorCopy(TreeNode root) {
        if (root == null) return null;
        TreeNode copy = new TreeNode(root.val);
        copy.left = mirrorCopy(root.right);   // old right goes on the left
        copy.right = mirrorCopy(root.left);   // old left goes on the right
        return copy;
    }
}

How long it takes: one visit per node, O(n). Extra room: a whole new tree of n nodes, O(n), plus the call stack. Use this when the caller must keep the original tree.

Way 2: the clever way

Do it in place, like the dance teacher. At each node, swap the two children. Then go into each child and do the same. The order does not matter much: you can swap first and then go down, or go down first and swap on the way back.

1. If the node is empty, stop.
2. Swap left and right. Each child brings its whole family with it.
3. Mirror the new left child, then the new right child.

class Solution {
    public TreeNode mirror(TreeNode root) {
        if (root == null) return null;
        TreeNode keep = root.left;     // hold the left side
        root.left = root.right;        // switch hands
        root.right = keep;
        mirror(root.left);             // now fix each side inside
        mirror(root.right);
        return root;
    }
}

How long it takes: one swap per node, O(n). Extra room: no new nodes, only the pile of waiting helpers, as tall as the tree, O(h).

Watch out for

• The empty tree. Return null right away.
• Mirroring is its own undo. Mirroring twice gives back the original tree, which is a quick self test.
• For a very deep stick shaped tree, recursion can overflow. Use a queue: take a node, swap its children, add the children to the queue. It is the same idea without the call stack.

What interviewers ask next

• Check if two trees are mirrors of each other. Walk both at once: compare a.left with b.right and a.right with b.left.
• Check if one tree is symmetric. It is symmetric when its left side is a mirror of its right side, which is the same check on the root's two children.
• Do it without recursion. Use a queue or a stack of nodes and swap the children of each node you take out. Every node still gets swapped exactly once.
• What does the inorder reading of a mirror look like? It is the original inorder reading backwards.

Remember this

Grown-up words: switching hands is swapping the child pointers, doing it to every node by going down first is a depth first search, the pile of waiting helpers is the call stack, and changing the tree without building a new one is working in place. The problem is also called invert binary tree.