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]

source: leetcode.com

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.

Advertisements

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)

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s