Invert Binary Tree

1. Define the problem

You are given a binary tree. Turn it into its mirror image : every node keeps its own number, but its left child and its right child swap places, all the way down the tree. To keep the input and the output easy to type and to check, the tree arrives as a level-order array such as [4, 2, 7, 1, 3, 6, 9], where null marks a missing child. Your function builds the real tree from that array, inverts it, and returns the inverted tree as a level-order array again. You never pass a tree object in or out. The fix is small: at each node, swap its two children , then do the same thing to each child. That is all inverting means.

Constraints

The number of nodes is between 0 and 100
-100 ≤ node value ≤ 100
Input is a level-order array with null for a missing child
Return the inverted tree as a level-order array with no trailing nulls

Example

Inputvalues = [4, 2, 7, 1, 3, 6, 9]

Output[4, 7, 2, 9, 6, 3, 1]

Explanation The root 4 swaps its children, so 7 moves to the left and 2 moves to the right. Then 7 swaps 6 and 9, and 2 swaps 1 and 3. Reading the new tree level by level gives [4, 7, 2, 9, 6, 3, 1].

2. Know the words first

In plain terms

Binary tree: A structure made of nodes. Each node holds a number and can point to at most two other nodes below it: a left child and a right child. The single node at the very top is called the root.
Level-order array: A way of writing a tree as a flat list. You read the tree top to bottom, left to right, one level at a time, and write null wherever a child is missing. [4, 2, 7, 1, 3, 6, 9] means 4 is the root, 2 and 7 are its children, and 1, 3, 6, 9 are the four nodes below them.
Recursion: A function that calls itself on a smaller piece of the same problem. Here, inverting a tree means swapping the top node’s two children and then asking the same function to invert each of those children.

3. Visualize the solution

The tree drawn as a level-order row (slot i has children 2i+1 and 2i+2)

Statusinit

Build the tree from the level-order array before touching anything.

What happens in this step

values = [4, 2, 7, 1, 3, 6, 9]

Slot 0 is the root 4.
Its children sit in slots 1 and 2 (values 2 and 7).
The four leaves fill slots 3 to 6.

Nothing has been swapped yet.

Step 1 of 6

Steps to visualize

Each cell is one slot of the tree read level by level: slot 0 is the root, slots 1 and 2 are its children, slots 3 to 6 are the four nodes under them.
Slot i always has its left child at slot 2i+1 and its right child at slot 2i+2.
Swapping a node’s two children moves whole subtrees, so several cells change at once.
Work from the top down: swap the root’s children first, then repeat inside each child.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The tree drawn as a level-order row (slot i has children 2i+1 and 2i+2)

Statusinit

Build the tree from the level-order array before touching anything.

What happens in this step

values = [4, 2, 7, 1, 3, 6, 9]

Slot 0 is the root 4.
Its children sit in slots 1 and 2 (values 2 and 7).
The four leaves fill slots 3 to 6.

Nothing has been swapped yet.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function invertTree(values) {
  function Node(value) {
    this.val = value;
    this.left = null;
    this.right = null;
  }

  function buildTree(list) {
    if (list.length === 0 || list[0] === null) {
      return null;
    }

    const root = new Node(list[0]);
    const queue = [root];
    let i = 1;

    while (i < list.length && queue.length > 0) {
      const node = queue.shift();

      if (list[i] !== null && list[i] !== undefined) {
        node.left = new Node(list[i]);
        queue.push(node.left);
      }

      i += 1;

      if (list[i] !== null && list[i] !== undefined) {
        node.right = new Node(list[i]);
        queue.push(node.right);
      }

      i += 1;
    }

    return root;
  }

  function toLevelOrder(node) {
    if (node === null) {
      return [];
    }

    const out = [];
    const queue = [node];

    while (queue.length > 0) {
      const current = queue.shift();

      if (current === null) {
        out.push(null);
        continue;
      }

      out.push(current.val);
      queue.push(current.left);
      queue.push(current.right);
    }

    while (out.length > 0 && out[out.length - 1] === null) {
      out.pop();
    }

    return out;
  }

  function invert(node) {
    if (node === null) {
      return null;
    }

    const temp = node.left;
    node.left = node.right;
    node.right = temp;

    invert(node.left);
    invert(node.right);

    return node;
  }

  const root = buildTree(values);

  invert(root);

  return toLevelOrder(root);
}

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

6. Test cases

Test cases

Input	Expected	Covers
`values = [4, 2, 7, 1, 3, 6, 9]`	`[4, 7, 2, 9, 6, 3, 1]`	example from the docstring
`values = [2, 1, 3]`	`[2, 3, 1]`	a root with two leaf children
`values = []`	`[]`	empty tree, nothing to invert
`values = [1]`	`[1]`	one node only, the answer is unchanged
`values = [1, 2]`	`[1, null, 2]`	a lone left child becomes a lone right child
`values = [1, 2, 3, 4, null, null, 5]`	`[1, 3, 2, 5, null, null, 4]`	a tree with gaps on both sides

Invert Binary Tree