Iron-On Transfer Flip

Easydepth-first searchAlso known as Invert Binary Tree

A print shop is making T-shirts for a family reunion. The design is a family tree drawn as boxes, each holding a person's id number, with at most two children under each box. Iron-on transfer paper prints everything mirror-image, so the shop must flip the design left to right before printing.

Flipping a picture does more than swap the two halves at the top. Every family branch, all the way down, ends up the other way round.

Your task

Write mirrorDesign(root). Turn the tree into its mirror image: at every node, the left subtree becomes the right subtree and the right becomes the left. Return the root of the mirrored tree. You may change the tree in place.

An empty tree stays empty. Trees are shown in level order, like [5, 3, 8, 1, 4, null, 9], where null marks a missing child. Your function receives and returns real TreeNode objects with val, left and right.

mirrorDesign(root: TreeNode) → TreeNode

Examples

Example 1

Input

root = [5, 3, 8, 1, 4, null, 9]

Output

[5, 8, 3, 9, null, 4, 1]

Why

5 stays at the top. Its children swap sides: 8 is now on the left, 3 on the right. Below them the same happens: 8's only child 9 moves to its left, and 3's children become 4 then 1. Read left to right, the bottom row was 1, 4, 9 and is now 9, 4, 1.

Example 2

Input

root = [1, 2]

Output

[1, null, 2]

Why

A lone left child becomes a lone right child. The swap must also move a child next to an empty slot, not only swap two existing children.

Constraints

0 ≤ number of people ≤ 1,000
-100,000 ≤ id ≤ 100,000
The tree is at most 500 levels deep.

Start with brute force

Read the tree level by level into rows, reverse each row, and rebuild a tree from the reversed rows. To make that work you have to keep every empty slot in each row, and a lopsided tree with 1,000 people can have rows with far more empty slots than people, because the slots double at every level.

You never need the rows. Mirroring is a purely local change: at each node, swap its two child pointers. Do that at every node once and the whole picture is flipped, in O(n) time with no extra copies.

Hints

0 of 4 shown

Hint 1
Hold the first example up to a mirror. The top box stays put. Where does box 1, the bottom-left corner, end up?
Hint 2
Box 1 moves to the bottom-right. That only happens if 3 moved to the right side and then 1 moved to the right side under 3. So the swap happens at every node, not only at the top.
Hint 3
Each subtree is a smaller design that also needs mirroring. If you could mirror the left and right subtrees on their own, what would be left to do at the root?
Hint 4
Recursion: for a null node return null. Otherwise mirror both subtrees, then attach the mirrored right subtree as the new left child and the mirrored left subtree as the new right child. Save one side in a variable before you overwrite it.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

A mirrored tree is the root, with the mirrored right subtree on its left and the mirrored left subtree on its right. That sentence is the whole algorithm.

Trace [5, 3, 8, 1, 4, null, 9]:

Mirror the subtree at 3. Its leaves 1 and 4 mirror to themselves, then swap: 3 now has 4 on the left and 1 on the right.
Mirror the subtree at 8. Its only child 9 was on the right; after the swap it is on the left.
Back at 5, swap the two finished subtrees: 8 goes left, 3 goes right.

Reading the result level by level gives [5, 8, 3, 9, null, 4, 1]. The two temporary variables matter: if you wrote root.left = mirror(root.right) first, the original left subtree would be lost before you mirrored it.

Reference solution

function mirrorDesign(root) {
  if (root === null) return null;
  const left = mirrorDesign(root.left);   // mirror each side first
  const right = mirrorDesign(root.right);
  root.left = right;                       // then swap them
  root.right = left;
  return root;
}

def mirror_design(root):
    if root is None:
        return None
    left = mirror_design(root.left)    # mirror each side first
    right = mirror_design(root.right)
    root.left = right                  # then swap them
    root.right = left
    return root

TimeO(n)Each node is visited once and does one swap.

SpaceO(h)The recursion stack, one call per level of the current path; h is the tree's height.

Learn the idea: Binary Trees Tree Traversals Recursion

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code