Community

Start a Thread


Notifications
Subscribe You’re not receiving notifications from this thread.

Invert a Binary Tree (Main Thread)

Here is the interview question prompt, presented for reference.

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 fuck off.— Max Howell (@mxcl) June 10, 2015

Given a binary tree like this:

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

Performing an inversion would result in:

Output:

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

The definition of a tree node is as follows:

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

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)

You can see the full challenge with visuals at this link.

Challenges • Asked over 3 years ago by Jake from AlgoDaily

Jake from AlgoDaily Commented on Nov 30, 2017:

This is the main discussion thread generated for Invert a Binary Tree.

Andre Commented on Mar 24, 2021:

Hey there,

Great exercise, thank you!
I wanted to point out the test case #3 is incorrect.
It defines inverted_tree2.right.left = Node(8) where it should actually be = Node(3).
As a consequence, my submission is failing that test and is not getting accepted.

Thank you!

Jake from AlgoDaily Commented on Mar 24, 2021:

Hi Andre,

Thanks for the heads up-- this is fixed!