Invert Binary Tree

Mirror a tree: swap every node's left and right children. Swap at the current node, then invert both subtrees (or the other way round); every node gets swapped exactly once.

Traced input: root = [4, 2, 7, 1, 3, 6, 9] → [4,7,2,9,6,3,1]. Original problem: neetcode.io/problems/invert-a-binary-tree

Complexity

One swap per node; recursion depth h.

Key idea

• Mirroring a tree = swap the children, then mirror each child.
• Pre-order and post-order both work; in-order does not (it re-swaps one side).
• Return the root so the call can be chained.

Common mistakes

• Overwriting root.left before saving it.
• Inverting only one level.

Solution

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

def invertTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    if not root: return None
    root.left, root.right = root.right, root.left
    invertTree(root.left)
    invertTree(root.right)
    return root

TreeNode* invertTree(TreeNode* root) {
    if (!root) return nullptr;
    swap(root->left, root->right);
    invertTree(root->left);
    invertTree(root->right);
    return root;
}

Edge cases

Each one has its own trace in the interactive view.