Valizada's blog

226. Invert Binary Tree - June day 1

Inspiration of this problem comes from Max Howel's interview experience with Google described in this tweet.

tweet

Lets jump to the problem

The idea is to invert every subtree, let's start with a simple example.

As you can see in the below example, just swap children nodes and we will have the resulting tree. Only leaf nodes

It gets a little trickier with bigger trees, however the principle is basic.

  • Start with root node
  • Swap its children
  • Perform the same process on all nodes

Let's this in an example:

Bigger tree

Now let's swap its children:

  1. Swap subtrees 3 and 7
  2. Swap subtrees of node 7: 6 and 9
  3. Swap subtrees of node 3: 2 and 4

Gif

Resulting tree will look like this:

Result

This can be solved using either depth first search or breadth first search, we will solve it with BFS to avoid recursion overhead:

  1. Create queue
  2. Add root to the queue
  3. While queue is not empty
  4. Remove first node from the queue
  5. If node is not null (not a lead node)
  6. Swap its left and right nodes
  7. Add left and right to queue
class Solution {
    public TreeNode invertTree(TreeNode root) {        
        var queue = new LinkedList<TreeNode>();
        queue.add(root);

        while(!queue.isEmpty()) {
            var node = queue.removeFirst();
            if(node != null) {
                var temp = node.left;
                node.left = node.right;
                node.right = temp;
                queue.add(node.left);
                queue.add(node.right);
            }

        }
        
        return root;
    }
}