Invert a binary tree

Easy TimeO(n) SpaceO(h)

Inverting a tree mirrors it: every node's left and right children change places, all the way down, so the tree comes back as its own reflection. Given the root of one, invert it and return the root. The swap applies at every node, not only at the root; the existing nodes are re-pointed rather than a new tree built; and an empty tree inverts to an empty tree.

Examples

Example 1

Input
node = invert(buildTree())out = []
Output
[4,7,9,6,2,3,1]
Read root first, the mirrored tree is 4, then 7, 9, 6, then 2, 3, 1.

Example 2

Input
node = buildTree()out = []
Output
[4,2,1,3,7,6,9]
The same tree before inverting — every pair of children now in the opposite order.

The Code

function buildTree() {
  return {
    val: 4,
    left: { val: 2, left: { val: 1, left: null, right: null }, right: { val: 3, left: null, right: null } },
    right: { val: 7, left: { val: 6, left: null, right: null }, right: { val: 9, left: null, right: null } }
  };
}
function invert(node) {
  if (node === null) return null;
  const left = invert(node.left);
  const right = invert(node.right);
  node.left = right;
  node.right = left;
  return node;
}
function flatten(node, out) {
  if (node === null) return out;
  out.push(node.val);
  flatten(node.left, out);
  flatten(node.right, out);
  return out;
}
flatten(invert(buildTree()), []);
Done

The first 9 calls, of 31. This one does not fit on a page.

Step through flatten(invert(buildTree()), []) call by call

More like this

All binary trees examples (9) →