Invert Binary Tree

The problem

A binary tree is made of nodes. Each node has a value, val, and two children, left and right. A child is another node, or null when it is missing. You are given root, the top node of a tree, or null for an empty tree. Invert the tree and return its root. Inverting makes the mirror image: at every node, the left child and the right child trade places. You may change the given nodes or build new ones. An empty tree stays empty, so return null for it.

What to write

type TreeNode = { val: number; left: TreeNode | null; right: TreeNode | null };

function solve(root: TreeNode | null): TreeNode | null

Input
root = {"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
{"val":2,"left":{"val":3,"left":null,"right":null},"right":{"val":1,"left":null,"right":null}}

Input
root = null

Output
null

Constraints

0–500 acyclic tree nodes; missing children are null.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The tree can be empty, so root may be null, and your code must not try to read the children of null. The tree can also be many levels tall, with up to 500 nodes, so the swap you see in example 1 has to happen at every level, not at the top only.

2. Hint 2: Ask a smaller question

   In example 1, swapping the two children of node 2 finishes the job. Now imagine nodes 1 and 3 had children of their own. After the swap at node 2, what would still be wrong, and where?

3. Hint 3: Name the pattern

   Each child, with everything below it, is a smaller tree: a subtree. Inverting a tree means inverting its two subtrees and swapping them, so the function can call itself on each child. That is recursion. The function's promise: given any node, return the inverted copy of the tree that starts there. Children are finished before their parent: postorder tree recursion. Read the lesson on postorder tree recursion.

4. Hint 4: State the invariant

   Every call returns the mirror image of the tree it was given, and null for a missing node. So when the two calls on a node's children come back, both subtrees are already inverted and only the swap at this node is left.

5. Hint 5: Sketch the pseudocode

   If the node is null, return null. Otherwise call the function on the left child and on the right child. Return a new node with the same value, whose left child is the inverted right subtree and whose right child is the inverted left subtree.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Recursively create each node with its original right subtree on the left and its original left subtree on the right.

The slow way

Swap the two children of the root and stop. In example 1 that is the whole job, because the root's children have no children of their own. In a taller tree it is not enough: the root's children have changed sides, but each of them, and every node further down, still has its own children on the old sides.

The insight

A child with everything below it is called a subtree. The mirror image of a tree has the mirror image of its right subtree on the left and the mirror image of its left subtree on the right. Those are the same job on smaller trees, so the function calls itself to do them: that is recursion. Children are finished before their parent, which is what postorder means.

Step by step

1. An empty tree is already its own mirror image. A missing node has nothing to swap, so the function returns null for it. This is also where the calls stop: every way down the tree ends at a missing child.
2. Invert the left subtree and the right subtree. The function promises one thing: given any node, it returns the inverted copy of the tree that starts there. So these two calls hand back both subtrees already inverted, however tall they are.
3. Build a new node with the two inverted subtrees on swapped sides. The inverted right subtree becomes the left child and the inverted left subtree becomes the right child. That is the swap for this node. Everything below was already swapped by the two calls.

The same numbered steps are the comments in each solution.

function solve(root) {
  // 1. An empty tree is already its own mirror image
  if (!root) return null;
  // 2. Invert the left subtree and the right subtree
  const invertedLeft = solve(root.left);
  const invertedRight = solve(root.right);
  // 3. Build a new node with the two inverted subtrees on swapped sides
  return { val: root.val, left: invertedRight, right: invertedLeft };
}

type TreeNode = {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
};
function solve(root: TreeNode | null): TreeNode | null {
  // 1. An empty tree is already its own mirror image
  if (!root) return null;
  // 2. Invert the left subtree and the right subtree
  const invertedLeft = solve(root.left);
  const invertedRight = solve(root.right);
  // 3. Build a new node with the two inverted subtrees on swapped sides
  return { val: root.val, left: invertedRight, right: invertedLeft };
}

def solve(root):
    # 1. An empty tree is already its own mirror image
    if root is None:
        return None
    # 2. Invert the left subtree and the right subtree
    inverted_left = solve(root.left)
    inverted_right = solve(root.right)
    # 3. Build a new node with the two inverted subtrees on swapped sides
    return TreeNode(root.val, left=inverted_right, right=inverted_left)

Example 1, traced

Input
root = {"val":2,"left":{"val":1,"left":null,"right":null},"right":{"val":3,"left":null,"right":null}}

Output
{"val":2,"left":{"val":3,"left":null,"right":null},"right":{"val":1,"left":null,"right":null}}

Why it works

A missing node is its own mirror image, so the function is right in the smallest case. For any other node, the two calls return the mirror images of its two subtrees, and placing each on the opposite side gives the mirror image of everything from that node down. So the function is right for every node, the root included.

Time and space

Time O(n), extra space O(n) output plus O(h) stack. The function runs once per node and once per missing child, with constant work each time: O(n) time. It builds one new node per node: O(n) for the output. The unfinished calls form a chain from the root down, one per level: O(h) on the call stack for h levels.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Check for the missing node before anything else. Without that check the function tries to read the children of null, and the program stops with an error on every input.
• If you change the given nodes instead of building new ones, keep the old left child in a variable before you overwrite the left side. Otherwise example 1 ends with 3 on both sides and the 1 is lost.
• Swap at every node, not only at the root. Exchanging the root's two children is enough in example 1, but in a taller tree the nodes further down keep their children on the old sides.

Pattern

Postorder tree recursion. Builds on Reverse Linked List.

Keep going