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
and1000000000
- 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
β
def invert_tree(head):
# fill in this method
return head
β
β
# Node definition
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
β
β
# Regular binary trees
tree1 = Node(4)
tree1.left = Node(1)
tree1.right = Node(3)
β
tree2 = Node(5)
tree2.left = Node(10)
tree2.left.left = Node(17)
tree2.left.right = Node(3)
tree2.right = Node(8)
β
# Binary search trees
tree3 = Node(6)
tree3.left = Node(3)
β
tree4 = Node(5)
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 our guided, illustrated walk-through.
How do I use this guide?
This is the famous question that Homebrew
author Max Howell
famously got wrong in a Google Interview. Hopefully this prevents you from having the same misfortune!
Let's think about brute force-- how would we do it without any clever algorithms? We can start with a very basic input as follows:
1 1
2 / \
32 3
So to invert it vertically, we'd start at 1
, where there's nothing to flip or swap, and it would stay put. We've now processed the first row.
Moving on to the second, we encounter 2
and 3
, so we'd swap them and get:
1 1
2 / \
33 2
Interesting, this seems to have inverted it! Is it as simple as swapping when there's more than one node?
What if we had more than two nodes to swap per level though? If there was an additional level, it might look like this:
1 1
2 / \
3 3 2
4 / \ \
5 4 5 3
That final row is currently directionally 4 -> 5 -> 3
, but we'd want the outcome to be 3 -> 5 -> 4
to be properly inverted.
However, we can achieve this by doing two separate swaps. Notice that the below is what we'd get if we swapped 4
and 5
to obtain 5 -> 4
, and then swapping 5 -> 4
with 3
.

1 1
2 / \
3 2 3
4 / / \
5 3 5 4
So, to put it all together: we can perform an in-order traversal and do a swap at each iteration.
A caveat that was pointed out by readers β if weβre dealing with a substantially large binary tree, then a recursive solution might cause problems due to call stack size. There are two ways to get around this:
- Using a stack to mimic the recursion
- Using a queue, visiting the levels one by one in a BFS fashion and swapping the left and right nodes to invert the tree.
Hereβs what the final code looks like:
1function invertTree(head) {
2 if (head) {
3 var temp = head.left;
4 head.left = head.right;
5 head.right = temp;
6
7 invertTree(head.left);
8 invertTree(head.right);
9 }
10
11 return head;
12}
Complexity of Final Solution
Let n
be the number of nodes in the binary tree. We traverse through all n
nodes using recursion for O(n)
time complexity, and we can have up to logn
recursive calls on the stack at once where logn
is the depth of the tree for O(logn)
space complexity.
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 ofO(n)
and space complexity ofO(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
thekey 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
and5
, followed by swapping5 -> 4
and3
, we can get3 -> 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 andO(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
print("Nice job, 4/4 tests passed!")
def invert_tree(head):
if not head:
return
β
if head.left or head.right:
temp = head.left
head.left = head.right
head.right = temp
β
invert_tree(head.left)
invert_tree(head.right)
β
return head
β
β
# Node definition
class Node:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
β
β
# Regular binary trees
tree1 = Node(4)
tree1.left = Node(1)
tree1.right = Node(3)
β
tree2 = Node(5)
tree2.left = Node(10)
tree2.left.left = Node(17)
tree2.left.right = Node(3)
Got more time? Let's keep going.
If you had any problems with this tutorial, check out the main forum thread here.