AlgoDaily - Invert a Binary Tree

Invert a Binary Tree (Hard)

Good morning! Here's our prompt for today.

You may see this problem at Flipkart, Oracle, Zillow, Snap, Intercom, Databricks, Twilio, Red Hat, Ibm, Lucid Software, Keeptruckin, Servicenow, Docusign, Sonos, and Electronic Arts.

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:

SNIPPET

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

Performing an inversion would result in:

SNIPPET

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

The definition of a tree node is as follows:

JAVASCRIPT

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)

xxxxxxxxxx
​
 
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);
​

OUTPUT

Results will appear here.