DEV Community

Cover image for Invert a Binary tree Leetcode solution
deepa
deepa

Posted on

Invert a Binary tree Leetcode solution

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

Top comments (2)

Collapse
 
vidit1999 profile image
Vidit Sarkar

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.

Collapse
 
deepa profile image
deepa

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