# Invert Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/invert-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/invert-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Oracle](https://scaleengineer.com/companies/oracle), [Ozon](https://scaleengineer.com/companies/ozon)
---
## Problem
Given the `root` of a binary tree, invert the tree, and return _its root_.

**Example 1:**

![](https://assets.glich.co/dsa/invert-binary-tree/image0.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/invert-binary-tree/image1.jpg) 

**Input:** root = [2,1,3]
**Output:** [2,3,1]

**Example 3:**

**Input:** root = []
**Output:** []

**Constraints:**

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

# Approaches
## Recursive Approach
We can solve this problem using a recursive approach where we swap the left and right children of each node recursively.
**Time:** O(n) where n is the number of nodes in the tree as we need to visit each node once · **Space:** O(h) where h is the height of the tree due to the recursive call stack. In worst case (skewed tree) it can be O(n)
**Pros:** Simple and easy to understand; Clean and concise code; Uses less space compared to iterative approach
**Cons:** Can cause stack overflow for very deep trees; Recursive calls may have overhead
### Explanation
The recursive approach works by traversing the binary tree and swapping the left and right children of each node. For each node:

1. First check if the root is null, if yes return null
2. Swap the left and right children of the current node
3. Recursively invert the left subtree
4. Recursively invert the right subtree
5. Return the root node

Here's the implementation:

```java
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) {
        // Base case: if root is null, return null
        if (root == null) {
            return null;
        }
        
        // Swap the left and right children
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        
        // Recursively invert left and right subtrees
        invertTree(root.left);
        invertTree(root.right);
        
        return root;
    }
}
```
### Algorithm
1. Check if root is null, return null if true
2. Store left child in temporary variable
3. Assign right child to left child
4. Assign temporary variable (original left child) to right child
5. Recursively call invertTree on left child
6. Recursively call invertTree on right child
7. Return root

## Iterative Approach using Queue
We can solve this problem iteratively using a queue to perform level order traversal and swap the children of each node.
**Time:** O(n) where n is the number of nodes in the tree as we need to visit each node once · **Space:** O(w) where w is the maximum width of the tree. In worst case (complete binary tree) it can be O(n/2) ≈ O(n)
**Pros:** Avoids recursion stack overflow; More intuitive for level-order processing; Better for very deep trees
**Cons:** Uses more space than recursive approach for most cases; Slightly more complex implementation; Additional data structure (queue) needed
### Explanation
The iterative approach uses a queue to perform a level-order traversal of the tree. For each node we encounter:

1. Remove the node from the queue
2. Swap its left and right children
3. Add the non-null children to the queue
4. Continue until the queue is empty

Here's the implementation:

```java
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;
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            
            // Swap the children
            TreeNode temp = current.left;
            current.left = current.right;
            current.right = temp;
            
            // Add non-null children to queue
            if (current.left != null) {
                queue.offer(current.left);
            }
            if (current.right != null) {
                queue.offer(current.right);
            }
        }
        
        return root;
    }
}
```
### Algorithm
1. If root is null, return null
2. Create a queue and add root to it
3. While queue is not empty:
   - Poll node from queue
   - Swap left and right children
   - Add non-null left child to queue
   - Add non-null right child to queue
4. Return root

# Solutions
### CSharp

```csharp
/** * Definition for a binary tree node. * public class TreeNode { * public int val; * public TreeNode left; * public TreeNode right; * public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) { * this.val = val; * this.left = left; * this.right = right; * } * } */ public class Solution { public TreeNode InvertTree ( TreeNode root ) { if ( root == null ) { return null ; } TreeNode l = InvertTree ( root . left ); TreeNode r = InvertTree ( root . right ); root . left = r ; root . right = l ; return root ; } }
```

### Java

```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 ) { dfs ( root ); return root ; } private void dfs ( TreeNode root ) { if ( root == null ) { return ; } TreeNode t = root . left ; root . left = root . right ; root . right = t ; dfs ( root . left ); dfs ( root . right ); } }
```

### JavaScript

```javascript
/** * 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) {
    const dfs = (root) => {
      if (!root) {
        return;
      }
      [root.left, root.right] = [root.right, root.left];
      dfs(root.left);
      dfs(root.right);
    };
    dfs(root);
    return root;
  };

```

### CPP

```cpp
/** * 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 ) { function < void ( TreeNode * ) > dfs = [ & ]( TreeNode * root ) { if ( ! root ) { return ; } swap ( root -> left , root -> right ); dfs ( root -> left ); dfs ( root -> right ); }; dfs ( root ); return root ; } };
```

### Python

```python
# 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 ]: def dfs ( root ): if root is None : return root . left , root . right = root . right , root . left dfs ( root . left ) dfs ( root . right ) dfs ( root ) return root
```