# Inverting a binary tree: probably easier than you think

## Problem Statement#

Write a function which takes in a binary tree, inverts it, and returns the inverted tree.

An inverted version of the tree above would swap every left node in the tree for its corresponding right node.

``````1class BinaryTree {2  constructor(value) {3    this.value = value4    this.left = null5    this.right = null6  }7}8/*9        INPUT10
11          112        /   \ 13       2     3      flip me!14     /  \   / \15    4    5 6   716   / \17  8   9            18
``````

Look down at your palms - they're mirror images of each other with respect to an imaginary line between your pinkies:

``````1/*      INPUT      |       SOLUTION2                   |3          1        |          1         4        /   \      |        /   \ 5       2     3    flip     3     26      / \   / \    ->     / \   / \7     4   5 6   7   |     7   6 5   48    / \            |              / \9   8   9           |             9   8   10                   |11
``````

## tl;dr#

• The solution is as simple as reassigning left & right pointers between nodes in one pass.
• Traversing a tree like this requires a queue to go breadth first instead of depth first.
• Leaf nodes' children, for the purposes of the queue, can be `null`; .This is important for space complexity calculations later.

## Solution#

### Brief#

Linked lists, trees, BSTs are often easy problems masquerading as difficult ones.

You may feel an inkling to traverse the tree depth-first (1 -> 2 -> 4) and re-construct the tree backwards somehow or traverse in some nebulous "opposite" fashion. However, the final tree is mirrored with respect to Y axis, not X. That should be a hint you're going in the wrong direction (up/down vs left/right)

Turns out, all you'll need is queue to parse the tree left to right, swapping each node's left and right values along the way.

A binary tree's node only has so much to offer. You have`node.value`, `node.left` and `node.right`:

``````1/*        1                  1         2        /   \               /   \ 3       2     3    flip     3     24
``````

Once you have that, you're done. Well, almost: you need to figure out how to apply the same actions to node 2, node 3, their children, and so on.

First, let's look at how to output the value of every "level" of a tree, left-to-right. As neat as recursion is, I think iterative solutions are easier to read:

``````1function printBinaryTreeValues(tree) {2    // initialize the queue. Our first element is the root3    const queue = [tree]4  5     // we'll be updating this guy as we go in lieu of using a recursive function6    let currentNode7
8    // while there something in the queue...9    while (queue.length > 0) {10        // yeet first item from the queue11        currentNode = queue.shift()12
13        // do something with node, in this case, print14        console.log(currentNode.value)15
16        // update the queue to handle the children nodes17        if (currentNode.left) queue.unshift(currentNode.left)18        if (currentNode.right) queue.unshift(currentNode.right)19
20        // next iteration will handle the newly added children 21        // preserving the left-to-right direction22    }23  // here, we are out of queue items24}25
``````

Let's go back to our smallest node "unit"...

### Swapper helper function#

``````1/*        12        /   \3       2     34
``````

Now you swap nodes with values 2 and 3. This logic will be applied to their children too, but for now, we're only looking at this one piece. Always be on the lookout as to what logic can be pawned off to its own function: don't clutter the meat of the solution or you may come to regret it. That regret comes when you're about 80% finished confidently explaining your way through a whiteboard problem.

Quickly swap values:

``````1// chad ES6 swap:2function swapNodeLeftAndRight(node) {3  [node.left, node.right] = [node.right, node.left]4}5// ugly, oldschool swap:6function swapNodeLeftAndRight(node) {7  const tempLeft = node.left8  node.left = node.right9  node.right = tempLeft10}11
``````

### Completed solution#

Finally, here is our iterative solution: (parse, swap left & right, enqueue children)

``````1// This is the class of the input binary tree.2class BinaryTree {3  constructor(value) {4    this.value = value5    this.left = null6    this.right = null7  }8}9
10function swapLeftAndRight(node) {11    [node.left, node.right] = [node.right, node.left]12}13
14function invertBinaryTree(tree) {15  const queue = [tree]16  let currentNode17  while (queue.length > 0) {18      currentNode = queue.shift()19      if (currentNode) swapLeftAndRight(currentNode)20      if (currentNode.left) queue.unshift(currentNode.left)21      if (currentNode.right) queue.unshift(currentNode.right)22    }23  }24
``````

## Big O: Time & Space Complexity#

Since this algorithm runs in one pass through all the tree's nodes (no nested loops, or other shenanigans) the time complexity is O(n).

As for space complexity - there's a queue growing in memory with every iteration. There's a little nuance to why this is so (touched on in the tl;dr) but the answer is O(n) as well, not O(1)