226. Invert Binary Tree 🚀
Tags: javascript, beginners, programming, leetcode
Published: 2022-05-16 19:31:00


### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode '[226. Invert Binary Tree](https://leetcode.com/problems/invert-binary-tree/)' question. This question is rated as a **Easy** question.

Question:

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

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

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

## Explaining The Question
We need to invert a binary tree. As if you held a **mirror** to the tree.
What this mean's is that at every `node`, we have to swap the `left` and `right` nodes. We continue this until we have no more nodes left. 

So by starting from the bottom of the tree, we will swap the `left` node with the `right` node and vice versa.

***

##  Recommended Knowledge
1. [Binary Trees](https://en.wikipedia.org/wiki/Binary_tree)
2. [Post Order Travel](https://en.wikipedia.org/wiki/Tree_traversal#Post-order)
3. [Array Destructuring. (ES6) (Optional)](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Destructuring_assignment)

## What do we know?
1. We have a tree and we gotta invert it. That is to say, `left` nodes become `right` nodes and `right` nodes become `left` nodes.

## How we're going to do it:

We're going to use a **Post Order Traversal** to invert the `tree`. Meaning, we will start at the very bottom left of the tree and work our way back up to the `root` of the tree. 

We're then going to swap the `left` and `right` nodes. We will do this to every node in the tree until we get back up to the `root` **node**

1. As we're going recursively, all we're going to do is swap the left and right nodes on every node we go to.
1. Firstly we do this by checking that a node exists at all. This is for edge cases and for when we reach the end of the tree.
1. We declare a temporary variable to hold the left node (As we're about to override it but still need it for later).
1. We then swap the left and right nodes. With the help of that temporary variable.
1. We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree. The order of this part does not matter, so long as you swap them.
1. Assuming we have swapped our left and right nodes, we return the root node. We do this because we're going to be calling this function recursively. So we can go back up in the stack. But this is mostly important for when we reached the last node in the stack.



## Big O Notation:
* Time Complexity:   *O(**n**)* | Where ***n*** is  *number of tree nodes* | Because we go over each node.
* Space Complexity: *O(**h**)* | Where ***h*** is  the *maximum height of the tree* | Because that will be the size of the call stack | Although it could be argued to be O(n) as the their is a worst case possibility of the call stack being as deep as the ENTIRE tree.

' ***Could this be improved?*** ' Yes! [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) could do this problem in ***O(1) space complexity***. But [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) is tricky and tough to read. For the sake of simplicity, I don't use it here. 


## Leetcode Results:

See Submission Link: 

* Runtime: 61 ms, faster than ***87.47%*** of JavaScript online submissions for Invert Binary Tree.
* Memory Usage: 47 MB, less than ***40.24%*** of JavaScript online submissions for Invert Binary Tree.

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/679682848/)


***

# Solution 1
```
	var invertTree = function (root) {
	/* -------------------------------------------------------------------------- */
	/*                           226. Invert Binary Tree                          */
	/* -------------------------------------------------------------------------- */

	// We have reached a leaf node, so we need to bubble back up the stack.
	// To the next node.
	if (!root) {
		return root;
	}

	// A temporary variable to hold the left node (As we're about to override it but still need it for later).
	let temp_node = root.left;

	// We then swap the left and right nodes. With the help of that temporary variable.
	root.left  = root.right;
	root.right = temp_node;

	// We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree.
	invertTree(root.left);
	invertTree(root.right);

	// Assuming we have swapped our left and right nodes, we return the root node.
	return root;
};
```

# Solution 2
```
 var invertTree = function (root) {

	// We have reached a leaf node, so we need to bubble back up the stack.
	// To the next node.
	if (!root) {
		return root;
	}
    
    // ES6 Destructuring.
    // What this does is take the left and right nodes and swap them.
    // But without the need of a temp variable. As in object destructuring, it remembers.
    // Although, if you're a performance fanatic, this isn't efficient. 
	[root.left, root.right] = [invertTree(root.right), invertTree(root.left)]
    
	return root
};

```