Inverting a binary tree: probably easier than you think

Spiciness: 🌶️🌶️ (poblano)

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 = value
4    this.left = null
5    this.right = null
6  }
7}
8/*
9        INPUT
10
11          1
12        /   \ 
13       2     3      flip me!
14     /  \   / \
15    4    5 6   7
16   / \
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      |       SOLUTION
2                   |
3          1        |          1         
4        /   \      |        /   \ 
5       2     3    flip     3     2
6      / \   / \    ->     / \   / \
7     4   5 6   7   |     7   6 5   4
8    / \            |              / \
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 havenode.value, node.left and node.right:

1/*        1                  1         
2        /   \               /   \ 
3       2     3    flip     3     2
4

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.

Traverse left-to-right (breadth-first)

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 root
3    const queue = [tree]
4  
5     // we'll be updating this guy as we go in lieu of using a recursive function
6    let currentNode
7
8    // while there something in the queue...
9    while (queue.length > 0) {
10        // yeet first item from the queue
11        currentNode = queue.shift()
12
13        // do something with node, in this case, print
14        console.log(currentNode.value)
15
16        // update the queue to handle the children nodes
17        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 direction
22    }
23  // here, we are out of queue items
24}
25

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

Swapper helper function

1/*        1
2        /   \
3       2     3
4

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.left
8  node.left = node.right
9  node.right = tempLeft
10}
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 = value
5    this.left = null
6    this.right = null
7  }
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 currentNode
17  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)

Spiciness: 🌶️🌶️ (poblano)

Problem Statement#

tl;dr#

Solution#

Brief#

Traverse left-to-right (breadth-first)#

Swapper helper function#

Completed solution#

Big O: Time & Space Complexity#