Invert Binary Tree

EasyTree Binary Tree DFS Recursion

When an app switches to a right-to-left language such as Arabic or Hebrew, its screen layout has to be mirrored. The app stores the layout as a binary tree of panels, and mirroring means that at every panel the left and right sub-panels trade places, all the way down the tree.

Given the root of the tree, mirror it in this way and return the root of the result. An empty layout (root is null) stays empty.

Example 1

Input: root = [8,3,10,1,6,null,14]
Output: [8,10,3,14,null,6,1]

Explanation: Every level now reads right to left: 3, 10 becomes 10, 3, and 1, 6, 14 becomes 14, 6, 1, with the empty spot moving to the other side.

Example 2

Input: root = [5,4,null,3]
Output: [5,null,4,null,3]

Explanation: A chain of left children turns into a chain of right children.

Example 3

Input: root = [7,null,9,8]
Output: [7,9,null,null,8]

Explanation: 9 moves to the left of 7, and its left child 8 moves to its right.

Constraints

The tree has at most 100 nodes.
Node values are integers from -100 to 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