Invert Binary Tree

easy tree dfs

Problem

Given the root of a binary tree, invert the tree, and return its root.

One DFS does the job: at each node, swap its two child links, then recurse into both children. The order (top-down vs bottom-up) doesn't matter for correctness.

Input"4, 2, 7, 1, 3, 6, 9"

Output"4, 7, 2, 9, 6, 3, 1"

tree (level-order, '_' for null)

def invert_tree(node):
    if node is None:
        return None
    node.left, node.right = node.right, node.left
    invert_tree(node.left)
    invert_tree(node.right)
    return node

function invertTree(node) {
  if (!node) return null;
  const tmp = node.left;
  node.left = node.right;
  node.right = tmp;
  invertTree(node.left);
  invertTree(node.right);
  return node;
}

class Solution {
    public TreeNode invertTree(TreeNode node) {
        if (node == null) return null;
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
        invertTree(node.left);
        invertTree(node.right);
        return node;
    }
}

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

Explanation

Inverting a tree means mirroring it left-to-right: every node's left child becomes its right child and vice versa, all the way down.

The neat thing is we do not need to do anything clever per node — just swap its two children. If we do that swap at every single node, the whole tree ends up mirrored.

To visit every node we use recursion (a depth-first search). At a node we swap its left and right links, then call the same function on both children. When we reach an empty spot (null), there is nothing to do, so we stop — that is the base case.

It does not matter whether you swap first then recurse, or recurse first then swap; either order mirrors the tree correctly.

Example: a tree 4 → (2, 7) becomes 4 → (7, 2), and the same flip happens inside each subtree.

Time: O(n) Space: O(h)