Good morning! Here's our prompt for today.

Can you invert a binary tree over its vertical axis? This is a famous problem made popular by this tweet:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f**k off.

— Max Howell (@mxcl) June 10, 2015

Given a binary tree like this:

1     4
2   /   \
3  2     7
4 / \   / \
51   3 6   9

Performing an inversion would result in:

1Output:
2
3     4
4   /   \
5  7     2
6 / \   / \
79   6 3   1

The definition of a tree node is as follows:

1function Node(val) {
2  this.val = val;
3  this.left = null;
4  this.right = null;
5}

Constraints

• Number of nodes in the tree <= 1000
• The nodes will always contain integer values between -1000000000 and 1000000000
• Expected time complexity : O(n)
• Expected space complexity : O(logn)

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

xxxxxxxxxx

  assertIsFunction(invertTree, '`invertTree` should be a function');

var assert = require('assert');

​

function invertTree(head) {

  return;

}

​

function Node(val) {

  this.val = val;

  this.left = null;

  this.right = null;

}

​

// Regular binary trees

var tree1 = new Node(4);

tree1.left = new Node(1);

tree1.right = new Node(3);

​

var tree2 = new Node(5);

tree2.left = new Node(10);

tree2.left.left = new Node(17);

tree2.left.right = new Node(3);

tree2.right = new Node(8);

​

// Binary search trees

var tree3 = new Node(6);

tree3.left = new Node(3);

​

var tree4 = new Node(5);

tree4.left = new Node(3);

Here's a video of us explaining the solution.

To change the speed of the video or see it in full screen, click the icons to the right of the progress bar.

Here's how we would solve this problem...

How do I use this guide?