# Solution For Invert Binary Tree

The Invert Binary Tree problem on LeetCode is a relatively simple problem that involves swapping the left and right children of all nodes in a binary tree. Below is a detailed solution to this problem using recursive function calls.

Problem Statement: Invert a binary tree.

Example:
Input:

`````` 4
``````

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

Output:

`````` 4
``````

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

Solution:
The basic idea behind this problem is to use a recursive function to invert the left and right children of each node in the binary tree.

The first step in the recursive function is to check if the root is null or not. If the root is null, we simply return as there is no need to invert an empty tree.

If the root is not null, we then create a temporary variable to store the left child of the root. We then recursively call the invert function on the left child to invert all of its children. We do the same thing for the right child of the root.

After the recursive calls are complete, we then swap the left and right children of the root using the temporary variable created earlier.

Finally, we return the root of the inverted tree.

Here is the Python code to implement this solution:

“`
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
if root is None:
return None

``````    # Recursively invert children of left and right subtrees
left = self.invertTree(root.left)
right = self.invertTree(root.right)

# Swap left and right children of current node
root.left = right
root.right = left

return root
``````

“`

Note that we define a TreeNode class to represent the nodes in the binary tree, with each node having a value, a left child, and a right child.

We then define the Solution class which contains the invertTree function. This function takes in a root node of the binary tree as an argument and returns the root node of the inverted tree.

We start by checking if the root is null. If it is, we simply return null.

If the root is not null, we then recursively call the invertTree function on the left child of the root and store the result in a variable ‘left’. We do the same thing for the right child of the root and store the result in a variable ‘right’.

After the recursive calls are complete, we then swap the left and right children of the root using a temporary variable. Finally, we return the root of the inverted tree.

The time complexity of this solution is O(n) where n is the number of nodes in the binary tree since we visit each node once. The space complexity of this solution is also O(n) since we store the call stack for each recursive call.

## Step by Step Implementation For Invert Binary Tree

```/**
* 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 the tree is empty, return null
if(root == null){
return null;
}

//create a temporary TreeNode to store the left child
TreeNode temp = root.left;

//swap the left and right children
root.left = root.right;
root.right = temp;

//recursively invert the left and right subtrees
invertTree(root.left);
invertTree(root.right);

return root;
}
}```
```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def invertTree(self, root: TreeNode) -> TreeNode:
# Base case - when root is None, return None
if not root:
return None

# Recursive case - swap left and right subtrees
root.left, root.right = root.right, root.left

# Recursively call invertTree on the left and right subtrees
self.invertTree(root.left)
self.invertTree(root.right)

# Return the root of the inverted tree
return root```
```Given a binary tree, invert the binary tree and return it.
Look at the example for more details.

Example :
Given binary tree

1
/   \
2     3
/ \   / \
4   5 6   7
invert and return

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

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @return {TreeNode}
*/
var invertTree = function(root) {
// if there is no root, return null
if(!root) {
return null;
}

// create a temp variable to store the left child
let temp = root.left;

// set the left child to the right child
root.left = root.right;

// set the right child to the temp variable (which holds the original left child)
root.right = temp;

// recursively call invertTree on the left and right children
invertTree(root.left);
invertTree(root.right);

// return the inverted tree
return root;
};```
```/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if(root==NULL)
return NULL;
TreeNode *temp=root->left;
root->left=root->right;
root->right=temp;
invertTree(root->left);
invertTree(root->right);
return root;
}
};```
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     public int val;
*     public TreeNode left;
*     public TreeNode right;
*     public TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode InvertTree(TreeNode root) {
//in case the tree is empty
if(root == null){
return null;
}
//swap the left and right child of each node
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;

//recursively invert the left and right subtrees
InvertTree(root.left);
InvertTree(root.right);

return root;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]