38. Invert Binary Tree

EasyTree Binary Tree DFS Recursion

Given the root of a binary tree, mirror it: at every node, the left and right subtrees trade places. Return the root of the mirrored tree.

Picture holding the tree up to a mirror. Whatever was on the far left ends up on the far right, at every level.

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Explanation: Each level reads right-to-left after the swap: 2,7 becomes 7,2 and 1,3,6,9 becomes 9,6,3,1.

Example 2

Input: root = [2,1,3]
Output: [2,3,1]

Example 3

Input: root = []
Output: []

Constraints

The number of nodes is in the range [0, 100]
-100 <= Node.val <= 100

💡 Hint 1

If you already had the mirrored versions of both subtrees, how would you build the mirror of the whole tree?

💡 Hint 2

Swap left and right at the current node, then recurse into both children. The empty tree is its own mirror.

💡 Hint 3

An iterative BFS or DFS works too: pop a node, swap its children, push the non-null ones.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Recursion mirrors the definition. An empty tree is already inverted. Otherwise, invert the right subtree and hang it on the left, invert the left subtree and hang it on the right, and return the node. Every node is visited once. The recursion depth equals the tree height, so a queue-based BFS that swaps children level by level is a safe alternative for very deep trees.

Time O(n)Space O(h), where h is the tree height

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

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

/**
 * Definition for a binary tree node (provided):
 * function TreeNode(val, left, right) { this.val = val ?? 0; this.left = left ?? null; this.right = right ?? null; }
 *
 * @param {TreeNode} root
 * @return {TreeNode}
 */
function invertTree(root) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit