Invert a binary tree

Swap the left and right child at every node to produce the mirror image of the tree.

The idea

Inverting a tree means every node's left and right subtrees trade places, all the way down. Recurse into both children first, then swap the two child references at the current node. Once every node has done this swap, the whole tree is a mirror image of the original.

Code

public static TreeNode Invert(TreeNode node) {
    if (node == null) return null;
    TreeNode left = Invert(node.left);
    TreeNode right = Invert(node.right);
    node.left = right;
    node.right = left;
    return node;
}

Tips

• The swap can happen before or after the recursive calls; the result is the same either way.

In the .NET library

This exact "swap children recursively" shape also mirrors an expression tree, and is the inverse operation used when checking whether a tree is symmetric.