#BlackLivesMatter Support An Initiative
Invert a Binary Tree

Let’s Invert A Binary Tree

If  you are familiar with the stories of software engineering interviews at the big tech companies like Google, then you have probably heard of or seen this tweet by Max Howell, the founder of Homebrew.

This question is inspired by his tweet and we’ll take a look at how to solve it. At the core, it is a very simple question (if you’re familiar with trees/graphs and binary trees).

A binary tree is a tree (hierarchical) data structure whose elements have at most 2 children. A Binary Tree node contains a data, left child and right child. Below is a general representation of a binary tree.

A binary tree

Inverting a binary tree in this case means, swapping the left and right children of a node of the tree.

Let’s try to see how we might invert a tree represented by an array. Given an array [9, 3, 5, 1, 5] represented as a tree, invert the elements within the array. The array will end up looking like this: [9, 5, 3, 5, 1].

The elements in the first array will map to the following:

9 -> root node

3 -> left child node of 9

5 -> right child node of 9

1 -> left child node of 3

5 -> right child node of 3

From the above, it means, we’ll need to traverse the tree and swap the left child node with the right child of our current node, starting from the root node. Below is a representation of the original and inverted tree (from the array above);

Invert a Binary Tree

[9, 3, 5, 1, 5]       ————————————->       [9, 5, 3, 5, 1]

 

As you can see, we simply traverse the tree and swap all children of the left node and then all children of the right node. We’ll use dynamic programming to recursively call an invertTree() function starting with the left node, and then the right child node of the current node. Here’s how it’ll look in code;

The above solution will run in O(n) time complexity, where n represents the number of nodes, and O(d) space complexity where d represents the depth of the binary tree.

Link to question on Leetcode: https://leetcode.com/problems/invert-binary-tree

Hopefully no one will ever ask an engineer to invert a binary tree on the job :). Cheers!

Leave a Comment

Your email address will not be published. Required fields are marked *