## Invert a Binary Tree

Asked in:Google, Amazon

Difficulty:Medium

#### Understanding the problem

**Problem description:** Invert a binary tree.

An inverted form of a Binary Tree is another Binary Tree with left and right children of all non-leaf nodes interchanged. You may also call it the mirror of the input tree.

**NOTE: **The tree is binary so there could be a maximum of two child nodes. This problem was originally inspired by this tweet by Max Howell .

Now, figure out that what does the interviewer mean when he says invert a binary tree, it would be helpful when you start looking at an example.

**Example 1**

**Example 2**

**Explanation : **You can observe that the root’s left pointer started pointing towards the right child and the right pointer towards the left child and a similar condition is noticed for all the sub root nodes.

The node structure for the BST passed to your function will be

```
class TreeNode
{
int val
TreeNode left
TreeNode right
}
```

**Recursive and iterative solutions**

We will be discussing three approaches to solve this problem

**Recursive solution (similar to pre-order traversal) :**Solve the problem by swapping the left and right child for the root of each subtree recursively.**Using Iterative Preorder Traversal :**We can convert the above recursive solution to iterative using stack.**Using Level order traversal :**iterative approach using queue

**1. Recursive Solution**

The key insight here is to realize that in order to invert a binary tree we only need to swap the children and recursively solve the two smaller sub-problems (same problem but for smaller input size) of left and right sub-tree. This looks similar to the idea of pre-order traversal.

The steps to be followed are :

- When the tree is empty return
**NULL**. This is also our base case to stop recursive calls. - For every node encountered we
**swap**its left and right child before recursively inverting its left and right subtree.

Pseudo Code

```
// Function to invert given binary Tree using preorder traversal
void invertBinaryTree(TreeNode root)
{
// base case: if tree is empty
if (root == Null)
return
// swap left subtree with right subtree
swap(root.left, root.right)
// invert left subtree
invertBinaryTree(root.left)
// invert right subtree
invertBinaryTree(root.right)
}
```

Complexity Analysis

In the above approach, we are traversing each node of the tree only once. **Time complexity**: O(n)

Space Complexity of this algorithm is proportional to the maximum depth of recursion tree generated which is equal to the height of the tree (h).

**Space complexity**: O(h) for recursion call stack, where h is the height of the tree.

Critical ideas to think

- Can we use idea similar to post-order traversal for solving this problem? or, can we use some other recursive idea for solution?
- Why recursion help us to solve the tree problems easily? Explore the properties of Pre-order, In-Order and Post-Order traversal.
- What is the space complexity in the worst and best-case scenario?

#### 2. Using **Iterative Preorder Traversal**

Here, a **Iterative Preorder Traversal** is used to traverse the tree using a LIFO stack. To convert recursive procedures to iterative, we need an explicit stack during the implementation.

Solution Steps

- When the tree is empty return
**NULL.** - Create an empty stack
**S**and push root node to stack. - Do following while
**S is not empty**:

- Pop an item from stack S and swap the left child with right child
- Push
**right child**of popped item to the stack S. - Push
**left child**of popped item to the stack S

Right child is pushed before left child to make sure that left subtree is processed first.

Pseudo Code

```
// Iterative Function to invert given binary Tree using stack
void invertBinaryTree(TreeNode root)
{
// base case: if tree is empty
if (root is null)
return
// create an empty stack and push root node
stack S
S.push(root)
// iterate until the stack is not empty
while (S is not empty)
{
// pop top node from stack
TreeNode curr = S.top()
S.pop()
// swap left child with right child
swap(curr.left, curr.right)
// push right child of popped node to the stack
if (curr.right)
S.push(curr.right)
// push left child of popped node to the stack
if (curr.left)
S.push(curr.left)
}
}
```

Complexity Analysis

For each node in the tree, we are performing push() and pop() operation only once. Total no of stack operations = 2n **(Think!)**

**Time complexity: **O(n), where n is the total number of nodes.

**Space Complexity: **O(n)**(Think!)**

Critical Ideas to think

- Visualize the stack operations via simple examples.
- Explore the best and worst case scenario of space complexity.
- Design iterative algorithms for in-order and post-order traversal (using stack).
- Can we solve this problem using level-order traversal?

**3. Using Level order traversal **

We can solve this problem using **Level Order Traversal. **Here we the traverse the tree using a **FIFO** Queue.

In each iteration :

- We are deleting one node from the queue :
**TreeNode curr = Q.dequeue()** - Swapping the left and right child :
**swap(curr.left, curr.right)** - Inserting left and right child to the queue

```
if (curr.left)
Q.enqueue(curr.left)
if (curr.right)
Q.enqueue(curr.right)
```

Pseudo Code

```
// Iterative Function to invert given binary Tree using queue
void invertBinaryTree(TreeNode root)
{
// base case: if tree is empty
if (root is NULL)
return
// maintain a queue and push push root node
queue Q
Q.enqueue(root)
// iterate untill queue is not empty
while (Q is not empty)
{
// pop top node from queue
TreeNode curr = Q.dequeue()
// swap left child with right child
swap(curr.left, curr.right)
// push left child of popped node to the queue
if (curr.left)
Q.enqueue(curr.left)
// push right child of popped node to the queue
if (curr.right)
Q.enqueue(curr.right)
}
}
```

Complexity Analysis

For each node in the tree, we are performing enqueue() and dequeue() operation only once. Total no of queue operations = 2n **(Think!)**

**Time complexity: **O(n), where n is the total number of nodes.

**Space Complexity: **O(n) (Think!)

Critical Ideas to think

- Can you use a similar approach if the tree is generic?
- Explore the best and worst case scenario of space complexity.
- Can we write a recursive code for level order traversal? If yes then, compare its performance with Iterative Implementation (level order traversal using queue).

#### Comparison of different solutions

#### Suggested Problem to solve

- Convert a given Binary tree to a tree that holds Logical AND property
- Create a mirror tree from the given binary tree
- Find mirror of a given node in a binary tree
- Convert binary tree to threaded binary tree
- Check if two binary trees are equal or not
- Convert a given tree to its Sum Tree

If you have any more approaches or you find an error/bug in the above solutions, please comment down below.

**Happy Coding! Enjoy Algorithms!**