Home/

...

/

Invert Binary Tree

Invert Binary Tree

Description

In this lesson, your task is to invert a given a binary tree, T.

Let’s look at an example below:

main.cpp
TreeNode.h
#include "TreeNode.h"
TreeNode* invertTree(TreeNode* root) {
    return root;
}
Invert binary tree

Solution

We can solve this problem using depth-first search (DFS).

The inverse of an empty tree is the empty tree. To invert tree T with root and subtrees left and right, we keep root the same and invert the right and left subtrees.

Let’s review the implementation below:

main.cpp
TreeNode.h
class TreeNode {
public:
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() {
        this-> val = 0;
    }
    TreeNode(int x) {
        this->val = x;
        this->right = nullptr;
        this->left = nullptr;
    }
    TreeNode(int x, TreeNode *left, TreeNode *right) {
        this->val = x;
        this->left = left;
        this->right = right;
    }
    ~TreeNode(){
        delete this->left;
        delete this->right;
    }
};
Invert binary tree

Complexity measures

Time Complexity Space Complexity
...

Access this course and 1200+ top-rated courses and projects.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy