Invert Binary Tree in JavaScript

The Prompt

Create a function that takes in a Binary Tree and inverts it. The function should swap every left node in the tree for its corresponding right node.

Note:

• Each Binary Tree node has an integer value, a left child node, and a right child node.
• The children nodes can either be BinaryTree nodes themselves or None/null.

The Code

First, we’ll create a queue variable and set it to an array containing the values of the (tree) input. Then enter into a while loop for as long as the queue contains elements. When the queue becomes 0, the while loop will end.

Next, we’ll create a new variable within the while loop, let’s call it (current). (current) will be set to the first element of the queue. Luckily, there’s a built in method that can do that for us, shift().

Now there’s an edge case here…. what if the queue is empty? That means the code will break at that point. For this case, we can use an if statement and allow the code to continue executing even if it meets the edge case scenario.

Now with the edge case out of the way, let’s add the logic for the swapping function.

Here, we’ll use some “aspirational code” and include another function (we’ll get to that soon).

The (swapLeftAndRight) function will act as the helper function. The helper function will take care of the swapping functionality. Using the given BinaryTree class and methods, the code should look similar to the following:

Now that the helper function is created and implemented into the solution, the final step would be to push the left and right nodes of (current) into the queue. The final code should look like this:

And that’s it!

Complexity Analysis

The time complexity of this solution is O(n) time, where (n) represents how many nodes there are in the tree input.

The space complexity is O(n) space, where (n) is the length of the elements being stored in the queue variable.