loading...
Cover image for Invert a Binary tree Leetcode solution

Invert a Binary tree Leetcode solution

deepa profile image deepa ・1 min read

The Leetcode June'20 challenge has begun with a tree inversion problem. The problem is pretty simple, invert a tree or in other words create a mirror image of the tree.
The implementation of the tree is given and is nothing different from the usual, containing left and right child for each node. To understand the problem a basic knowledge of binary tree is required. However, if you are well-versed with this data structure, the solution is quite easy to figure out.

Here's a link to the problem, try it on your own before you go through the solution below. (https://leetcode.com/explore/challenge/card/june-leetcoding-challenge/539/week-1-june-1st-june-7th/3347/)

Approach:

Travelling downward from the root of the tree, swap left and right child and call this same function recursively for each node of the tree. Pretty simple, eh?

C++ code:

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        TreeNode *i= root;
        TreeNode *temp=NULL;
        while(i!=NULL)
        {
            temp=i->left;
            i->left=i->right;
            i->right=temp;
            TreeNode *l=invertTree(i->left);
            TreeNode *r=invertTree(i->right);
            if(i==root)
                break;
        }
        return root;
    }
};

Posted on Jun 1 by:

Discussion

markdown guide
 

Thanks for the problem and solution. Here is my solution,

void invertTree(node* root){
    if(root){
        invertTree(root->left);
        invertTree(root->right);
        swap(root->left, root->right); // #include <algorithm> for this
    }
}

Note: It changes the tree in-place.

 

gotta say your solution is prettier( and efficient), thanks for sharing!