# Invert Binary Tree (Leetcode #226)

Given the `root` of a binary tree, invert the tree, and return *its root*.

**Example 1:**

![](https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg align="left")

```python
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg align="left")

```python
Input: root = [2,1,3]
Output: [2,3,1]
```

**Example 3:**

```python
Input: root = []
Output: []
```

**Constraints:**

* The number of nodes in the tree is in the range `[0, 100]`.
    
* `-100 <= Node.val <= 100`
    

### Answer

This answer can be done in many ways but I choose to do it via DFS or Depth First Search. DFS will go along one path as far as possible then back track and repeat the method.

To reverse a binary tree we can write out a function to reverse the binary tree and then using DFS to call it on their children.

```python
        if not root:
            return root
        temp = root.left
        root.left = root.right
        root.right = temp
```

In this section, we are doing two things. First, we check if the tree is empty and if it is we can return it immediately. Second we are writing a code to swap the node of the binary tree. After we finish writing our function to swap the node now we can call DFS.

```python
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
```

This code will keep going down the left path as far as possible and the backtrack to do the right path which will look something like

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1722094879150/04433a20-64f9-4349-8651-c980672377ac.png align="center")

Combing everything our answer will be

```python
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        temp = root.left
        root.left = root.right
        root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root
```

**Time Complexity:**  
We are visiting each node ounce and the swaping time complexity is O(1). Hence O(1) \* N = O(N) time complexity.

**Space Complexity**

This will depend on the balance of the tree since the space complexity is depends on the recursion stack.

1. If the tree is balanced then the recursion stack is O(logN)
    
2. If the tree is unbalanced the worst case stack is O(N)
    

Hence time complexity is in the best case O(logN) and worst case O(N)