Leetcode: Invert a Binary Tree

 

This question is asked at Microsoft, Amazon, Google, Facebook, eBay, and Paypal. Also, it is covered extensively in AlgoExpert. 

The question is as follows:

Given the root of a binary tree, invert the tree and return its root. Here are some examples of what is to be. Notice that the left is switched to the right sections for ALL levels, and vice versa: 

We can do this recursively. To do this, we first recursively call the switching method and subsequently switch the left and right sides of the binary tree. 

Here is the code for switching:

class Solution {

    public TreeNode invertTree(TreeNode root) {

        if(root == null) return null;

        //recursively move down the right tree

        TreeNode right = invertTree(root.right);

        //recursively move down the left tree

        TreeNode left = invertTree(root.left);

        //switch the nodes

        root.left = right;

        root.right = left;

        //return the root node which will be the same thing. Pass up on the tree. 

        return root;

    }

}

The time complexity is O(n). 

There is another approach and it is iterative, similar to breadth-first search. 

public TreeNode invertTree(TreeNode root) {

    if(root == null) return null;

    Queue<TreeNode> queue = new LinkedList<TreeNode>();

    queue.add(root);

    //poll the queue 

    //switch the queue

    //add the children of the queue

    while(!queue.isEmpty()) { 

        TreeNode current = queue.poll();

        TreeNode temp = current.left;

        current.left = current.right;

        current.right = temp;

        if(current.left != null) queue.add(current.left);

        if(current.right != null) queue.add(current.right);

    }

    return root;

}