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!:)

Advertisements

4 thoughts on “Invert a Binary Tree

  1. 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;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s