Invert Binary Search Tree

Invert a binary tree.

Example:

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

to

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

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

Trees are crucial data structure in Computer Science. Often trees related problems are solved using recursion as it provides an elegant solution in this particular problem at least. The basic terminology to solve this problem is to swap the left and right values, if you work on the tree from the bottom the to the top swapping the left and right node, the tree will be inverted.

Let's go through an example:

You can start from left or right. So, starting from the left we have

 

  2          2       (swap the left and right node)
 / \   =>   / \ 
1   3      3   1

  7          7       (similarly, on the right sub-tree)
 / \   =>   / \ 
6   9      9   6 

Which gives, 

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

And finally,

     4    (swap again)
   /   \
  7     2
 / \   / \
9   6 3   1

Translating it into code:

  public TreeNode invertTree(TreeNode root) {
        
        if(root == null)  //base case
            return null;
        
         root.left = invertTree(root.left); //recursive call 
         root.right = invertTree(root.right); 
        
         TreeNode temp = root.left; //swap the nodes
         root.left = root.right;
         root.right = temp;
        
        return root;
}

Another concise version:

public TreeNode invertTree(TreeNode root) {
        
        if(root == null)  //base case
            return null;
         TreeNode temp = root.left; //swap the nodes
         root.left = invertTree(root.right); //recursive call 
         root.right = invertTree(temp); 
        return root;
    }

Please do leave a comment if you found this helpful or want to share your idea/thoughts to improve.