Is Inverting a Binary Tree That Hard? Testing the Rumor

Back in June 2015, Max Howell, the creator of Homebrew, interviewed at google and was asked to invert a binary tree. Aparently he couldn't come up with a solution, and he was rejected. Afterward, He posted a tweet saying that google told him 90% of there engineers uses Homebrew, but he can't invert a binary tree on a whiteboard!

Appetizer#

A binary tree is a way of organizing data, where each item called a node and can point to at most two nodes, usually called left child and right child.

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

In order for the problem to be considered solved. The Left node becomes the right node and the right node becomes the left node. So the result would be the following:

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

How would you go about it? Feel free to pause and give it a thought! And btw this problem has the easy tag on leetcode, so it is considered an easy problem.

Have you guessed that it's looking like a bfs traversal? If not, hold on for a sec!

Why it's easy on LeetCode but looks confusing?#

Here’s the trick: if you think about it in its raw form, you might not reach the optimal solution. Instead, you end up trying to brute force it with too many if statements, handling cases one by one.

Usually, every problem falls under a certain pattern. Once you are familiar with the patterns, you’ll notice that this is a tree traversal problem. We can traverse the tree level by level, and on each level, we swap each node’s left and right children.

You might ask, “How do I get familiar with these patterns?” The only way is to solve problems grouped by pattern until you internalize them. NeetCode does a great job of this by organizing problems by pattern, give it a look!

Pseudo#

1. create a queue
2. insert the root node to the queue
3. loop while the queue length is bigger then zero
   1. consume the node from the queue
   2. swap its left and right childes
   3. push them to the queue

Let's give it a try using Go#

 type TreeNode struct {
     Val int
     Left *TreeNode
     Right *TreeNode
  }
 
func invertTree(root *TreeNode) *TreeNode {

   if root == nil {
      return nil
   }

   // we use a queue to store the nodes of each level
   queue := []*TreeNode{}

   queue = append(queue, root)
   
   for len(queue) > 0 {
		node := queue[0]
		queue = queue [1:]
		
		node.Left, node.Right = node.Right, node.Left

		if node.Right != nil {
			queue = append(queue, node.Right)
		}
		
		if node.Left != nil {
			queue = append(queue, node.Left)
		}

   }
   return root
}

Conlusion#

I think the take away from this, is that it's very important to internalize the patterns. As you can see we can do clean and efficient solutions using them.

That was it, A short one!