Invert Binary Tree

Invert Binary Tree

Invert a binary tree.

Example :

Input:

      7
    /   \
   9     5
  / \   / \
 1   10 3   6

Output:

      7
    /   \
   5     9
  / \   / \
 6   3 10   1

Solution:

This problem is best-suited for recursive approach.

Here, we see that inverse of a left node is the right node and inverse of left node of the previous left node is the right node of the previous right node and so on.
This suggests of some resursive calls untill we reach at the end of the tree.

Implementation:

Java:

/**
 * 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 right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;
        return root;
    }
}

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(n).