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.
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
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.
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);
[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;
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
if (root === null) return root;
swapLeftAndRightNodes(root);
invertTree(root.left);
invertTree(root.right);
return root;
};
var swapLeftAndRightNodes= function(root) {
const temp = root.left;
root.left = root.right;
root.right = temp;
};
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!