# [Leetcode #226.](https://leetcode.com/problems/invert-binary-tree/) Invert Binary tree
###### tags:`Binary tree` `Easy`
## Problem
Given the `root` of a binary tree, invert the tree, and return *its* root.
### Sample Input/Output
**Example 1**
```javascript
Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]
```
**Example 2**
```javascript
Input: root = [2,1,3]
Output: [2,3,1]
```
**Example 3**
```javascript
Input: root = []
Output: []
```
<br>
:::spoiler **Optimal Space & Time Complexity**
```!
Time O(n) | Space O(n) - where n is the number of nodes in the tree.
Note: Because of recursion, O(h) function calls will be placed on the stack in the worst case, where hhh is the height of the tree. Because h∈ O(n)h\in O(n)h∈O(n), the space complexity is O(n)O(n)O(n).
```
:::
<hr/>
## Solutions
### Official
**Recursive**
> This is a classic tree problem that is best-suited for a recursive approach.
```python=
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
right = self.invertTree(root.right)
left = self.invertTree(root.left)
root.left = right
root.right = left
return root
```
Since each node in the tree is visited only once, the time complexity is `O(n)`, where `n` is the number of nodes in the tree. We cannot do better than that, since at the very least we have to visit each node to invert it.
Because of recursion, `O(h)` function calls will be placed on the stack in the worst case, where `h` is the height of the tree. Because `h ∈ n`, the space complexity is `O(n)`.
<br>
**Iterative**
> Alternatively, we can solve the problem iteratively, in a manner similar to breadth-first search.
```python=
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
queue = collections.deque([root])
while queue:
current = queue.popleft()
current.left, current.right = current.right, current.left
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
return root
```
Since each node in the tree is visited / added to the queue only once, the time complexity is `O(n)`, where nnn is the number of nodes in the tree.
Space complexity is `O(n)`, since in the worst case, the queue will contain all nodes in one level of the binary tree. For a full binary tree, the leaf level has `⌈n/2⌉ = O(n)` leaves.
<br>
---
### Everyone's
**Recursive**
:::spoiler 月
conditional statement in line 4 can be simplified
```javascript=
// Time O(n) || Space O(n)
// where n is the number of nodes in the tree
var invertTree = function(root) {
if(!root || (!root.left && !root.right)) return root;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root
};
```
:::
<br>
:::spoiler 東
The worst case (a totally unbanlanced tree) should be considered upon space complexity (the call stack)
```javascript=
/*
Time O(n) | Space O(log(n)); n is the number of nodes
*/
var invertTree = function(root) {
if(!root) return null;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
};
```
:::
<br>
:::spoiler YC
The worst case (a totally unbanlanced tree) should be considered upon space complexity (the call stack)
```javascript=
/*
time: O(n) - where n is the number of nodes in the tree.
space: O(h); - where h is the height of the tree
*/
var invertTree = function(root) {
if(!root) return root;
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
return root;
};
```
:::
<br>
**Iterative**
:::spoiler Hao
If the input is a balanced tree. Recursion would cost less
```javascript=
/**
* Time complexity: O(n) where n stands for numbers of nodes in the tree
* Space complexity: O(n) where n stands for numbers of nodes in the tree
*/
var invertTree = function(root) {
const queue = [];
queue.push(root);
while (queue.length) {
const node = queue.shift();
if (node !== null) {
[node.left, node.right] = [node.right, node.left];
queue.push(node.left);
queue.push(node.right);
};
}
return root;
};
```
:::
---
## Supplement / Discussion
Sign in with Wallet
Connect another wallet