# Invert Binary Tree LeetCode Solution

Difficulty Level Easy

## Problem Statement:

Invert Binary Tree LeetCode Solution – In this question, Given a root of any binary tree, the solution is required to invert the binary tree meaning the left tree should become the right tree and vice versa. ## Explanation

We can ask ourselves which tree traversal would be best to invert the binary tree. Preorder is a pretty simple and readable solution. Our solution would be recursive.  Here are the steps :

1. The function will take root as an argument.
2. Swap root of left and right subtree.
3. invert left binary subtree.
4. invert right binary subtree.
5. return root once every subtree is inverted.

### Iterative Version

Here we can use a Preorder Traversal to traverse the tree (same idea if you prefer Inorder, but you’ll need to modify the code a little bit). First, you construct a `stack` to store `TreeNode*`s and pop out one at a time to process it. if the stack is empty, which means even the up-most root node and its right node is processed, then we can safely jump out of the loop. The only point is that when we’ve done the `swap`, we were supposed to do `t = t->right`, but here since we’ve swapped the left and the right node, the `right` should be currently the `left` node.

## Python Solution:

```# 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: Optional[TreeNode]) -> Optional[TreeNode]:
if root == None:
return root
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root```

## Java Solution:

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

## Time complexity for Invert Binary Tree LeetCode Solution:

O(N)

We will visit each node only once so O(N) would be the Time complexity.

## Space Complexity:

O(N)

In the worst case, if the binary tree is a skewed tree(only one child), the recursion call stack would need O(N) memory.

Translate »