DEV Community

Cover image for Invert a Binary tree Leetcode solution
deepa
deepa

Posted on

1

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

Image of Timescale

🚀 pgai Vectorizer: SQLAlchemy and LiteLLM Make Vector Search Simple

We built pgai Vectorizer to simplify embedding management for AI applications—without needing a separate database or complex infrastructure. Since launch, developers have created over 3,000 vectorizers on Timescale Cloud, with many more self-hosted.

Read more →

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!

Image of Docusign

🛠️ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more