Interview Course Based on Story Questions

# Description

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

Let’s look at an example below:


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

#include "TreeNode.h"
TreeNode* invertTree(TreeNode* root) {
    return root;
}

class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

from TreeNode import *
def invert_tree(root):
  pass

Python

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode() {}
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
    }
}

class Solution {
    public static TreeNode invertTree(TreeNode root) {
        return root;
    }
}

Java

export class TreeNode{
    constructor(val=0, left=null, right=null){
        this.val = val
        this.left = left
        this.right = right
    }
}

import {TreeNode} from './TreeNode.js'

function invertTree(root){
  
}

# 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:

TreeNode* invertTree(TreeNode* root) {
    if (root == nullptr) {
        return root;
    }
    TreeNode* right = invertTree(root->right);
    TreeNode* left = invertTree(root->left);
    root->left = right;
    root->right = left;
    return root;
}

int main(){
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    auto res = invertTree(root);
    print(root);
    return 0;
}

from TreeNode import *
def invert_tree(root):
    if root is None: 
      return root

    right = invert_tree(root.right);
    left = invert_tree(root.left);
    root.left = right;
    root.right = left;
    return root;


# Driver Code
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

print_tree(invert_tree(root))

class Solution {
    public static TreeNode invertTree(TreeNode root) {
        if (root == null) {
        return root;
    }
        TreeNode right = invertTree(root.right);
        TreeNode left = invertTree(root.left);
        root.left = right;
        root.right = left;
        return root;
    }
    public static void main(String args[]){
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);

        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        Utility.print(invertTree(root));
    }
}

function invertTree(root){
    if (root == null)
      return root

    var right = invertTree(root.right)
    var left = invertTree(root.left)
    root.left = right
    root.right = left
    return root
}

// Driver Code
var root = new TreeNode(1)
root.left = new TreeNode(2)
root.right = new TreeNode(3)
root.left.left = new TreeNode(4)
root.left.right = new TreeNode(5)

root.right.left = new TreeNode(6)
root.right.right = new TreeNode(7)

printTree(invertTree(root))

# Complexity measures
| **Time Complexity** | **Space Complexity** |
| --- | --- |
| $O(N)$ | $O(N)$ |
## Time complexity
The time complexity will be $O(N)$, where `N` is the number of nodes in the tree and we have to visit all the nodes once.
## Space complexity
The space complexity will be $O(N)$, where `N` is the number of nodes in the tree. In the worst case, the tree's `height` is equal to `N` for a skewed tree. Hence, in the worst case, we will have a space complexity of `O(N)`.