# Invert a Binary Tree

What makes this question special is this tweet.

He questions the interview process, I am with him. But whatever it is, it is.

Question : Invert a binary tree. Return the root of the inverted tree.

```     4
/   \
2     7
/ \   / \
1   3 6   9

to

4
/   \
7     2
/ \   / \
9   6 3   1```

I would request you to change tabs or minimize your browser and give a good 30-40 minutes before seeing the solution.

Solution :-
As you can see in the example, all nodes have their siblings inverted or swapped! So we can recursively swap siblings for every node. But we cannot do it in one function, hence using another function to do the recursion work is required.

```void inv(TreeNode* root){
if(root==NULL)
return;

swap(root->left, root->right);

inv(root->left);
inv(root->right);
}

TreeNode* Solution::invertTree(TreeNode* root) {
inv(root);
return root;
}
```

The Time Complexity : O(n)
, since each node is visited once. Here n is the number of nodes.
The Space Complexity : O(h), as this many function calls will be put on the stack in the worst case, here h is the height of the binary tree. h ∈ O(n)

The full working code is available at Github, you can star the repository to get updates. I am also maintaining an Interview-Question-Wiki, kindly star and contribute. You can also follow this blog for more such posts. Comment in your queries, report bugs, discuss! ## 4 thoughts on “Invert a Binary Tree”

1. Kunaal Jain

We can improve bounds for h to O(log(n));

Like

• sidgupta234

How can we do that Kunaal? In the skewed tree height would be of O(n).

Like

2. Vishal Khanna

We could combine the recursive call and swapping process using a temporary variable. Take a look at my approach.

node* invert_bt(node* root)
{
if(!root)
return NULL;

node *temp = invert_bt(root->left);
root->left = invert_bt(root->right);
root->right = temp;

return root;
}

Liked by 1 person

• sidgupta234

Bottoms up!! Oh yes, this would work. Will update by post soon. Thank You! 😀

Like

This site uses Akismet to reduce spam. Learn how your comment data is processed.