One Pager Cheat Sheet

• We can invert a binary tree over its vertical axis, resulting in the reversing of the node values between the left and right subtrees, with a time complexity of O(n) and space complexity of O(logn).
• Max Howell's misfortune in getting an infamous Google Interview question wrong reminds us to revert to the basics of brute force when confronted with a challenging problem.
• We swap the key values of successive rows to invert a binary tree vertically.
• The process of swapping two nodes with more than one node per level could result in the inversion of a binary tree.
• By swapping 4 and 5, followed by swapping 5 -> 4 and 3, we can get 3 -> 5 -> 4 to correctly invert the binary tree.
• We can swap the left and right nodes at each iteration by either a recursive stack solution or a queue BFS technique, resulting in an O(n) time and O(logn) space complexity.

This is our final solution.

To visualize the solution and step through the below code, click Visualize the Solution on the right-side menu or the VISUALIZE button in Interactive Mode.

xxxxxxxxxx

}

var assert = require('assert');

​

function invertTree(head) {

  if (head) {

    var temp = head.left;

    head.left = head.right;

    head.right = temp;

​

    invertTree(head.left);

    invertTree(head.right);

  }

​

  return head;

}

​

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

​

Alright, well done! Try another walk-through.

If you had any problems with this tutorial, check out the main forum thread here.