Invert Binary Tree

Given a tree , invert it.

That is its left node becomes its right node and this follows for every node in each level of the tree.

Similarly for the right node.

For example:

Given the tree:

 [4,2,7,1,3,6,9]

The output is :

[4,7,2,9,6,3,1]

Try out the solution here:

https://leetcode.com/problems/invert-binary-tree/

Solution:

Use DFS or BFS

Approach 1 – Depth First Search

In this approach you flip the left and right nodes recursively.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        
        if(root == null ) return null;
        
        TreeNode left = invertTree(root.right);
        
        TreeNode right  = invertTree(root.left);
        
        root.left = left;
        
        root.right = right;
        
        return root;
        
    }
}

As you see you recursively assign the right node of a tree to its left node and similarly the other way around.

Time complexity:

Since we traverse through each node time complexity is O(n)

Space complexity:

On the worst case we do a recursive call for every node , so a recursion stack of space O(n) is required.

Approach 2 – Use Breadth First Search:

As usual with BFS we use queues.

First you add the root node to the queue.

Then for each element in the queue:

Pop the first node

Create a temporary node left which points to the right node of the popped out node

Create a temporary node right which points to the left node of the popped out node.

Assign these new left and right nodes to the left and right of the popped out node.

Put the left and right nodes into the queue back so that the same can be done for them and their children using the queue.

Here is the code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode invertTree(TreeNode root) {
        
        if(root == null ) return null;
        
      
        
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        
        
        queue.add(root);
        
        
        while(!queue.isEmpty()){
            
            
            TreeNode n = queue.poll();
            
            if(n == null) continue;
            TreeNode l = n.right;
            
            TreeNode r = n.left;
            
            
            n.left = l;
            
            n.right = r;
            
            queue.add(l);
            queue.add(r);
            
            
        }
        
        return root;
    }
}

Algorithm:

1. If root is null return null
2. Add the first node to a queue
3. While queue is not empty do the following:
4. Pop the top node from queue
5. If it is null then continue (pop the next top node)
6. Create a temporary left node which points to the right node of the popped node
7. Create a temporary right node which points to the left node of the popped node
8. Point the left and right node of the popped node to the new left and right nodes
9. Add left node to the queue
10. Add right node to the queue
11. Return root node after the queue becomes empty

Time complexity:

Since we traverse through each node time complexity is O(n)

Space complexity:

Since every node is put into the queue space complexity is O(n)