Let's start with the description for Invert Binary Tree:

Given the

`root`

of a binary tree, invert the tree, and returnits root.

For example:

Although this one has a very simple recursive solution, let's see one approach that I come up with initially:

```
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
let queue = [];
queue.push(root);
while (queue.length > 0) {
let currentNode = queue[0];
if (currentNode !== null) {
queue.push(currentNode.left);
queue.push(currentNode.right);
[currentNode.left, currentNode.right] = [currentNode.right, currentNode.left];
}
queue.shift();
}
return root;
}
```

This version uses level-order traversal; we store the children of each node in a queue as we go through each level in the tree, and swap the node's left and right children.

#### Time and space complexity

Since we visit each node once, the time complexity is
$O(n)$
.

The space complexity will be proportionate to the size of the queue we keep, which holds a whole level at a time, which amounts to
$O(n)$
overall.

Now, let's look at the recursive solution, which is much simpler:

```
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val === undefined ? 0 : val)
* this.left = (left === undefined ? null : left)
* this.right = (right === undefined ? null : right)
* }
* }
*/
function invertTree(root: TreeNode | null): TreeNode | null {
if (root === null) {
return null;
}
[root.left, root.right] = [root.right, root.left];
invertTree(root.left);
invertTree(root.right);
return root;
}
```

#### Time and space complexity

The time complexity is $O(n)$ as we visit each node to swap its left and right children. The space complexity is also $O(h)$ —where $h$ is the height of the tree—because of the recursive calls to the function on each level.

Next up is Maximum Depth of Binary Tree. Until then, happy coding.

## Top comments (0)