Invert Binary Tree (Leet Code-266)

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code problem number 226. This is a Leet code problem named Invert Binary Tree. We will solve it using python and it is the best space and time-optimized solution.

Question of Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root..

The approach is to locate the binary tree by using another one that has all of its left and right child nodes switched. You may also state that your task is to locate the binary tree’s mirror image along its vertical axis.

Example

Example 1

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2

Input: root = [2,1,3]
Output: [2,3,1]

Example 3

Input: root = []
Output: []

Constraints

The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100

Approach to solve Invert Binary Tree

To solve this problem we will do a preorder traverse of the tree, swap the left and right children of each node, and then recursively invert the left and right subtree of each node. The tree can also be explored in a postorder method.

Algorithm

This method performs the following steps for a given input binary search tree:

Check base condition i.e. if the node is none then return root.
Swap the left and right children of the node.
Call the function recursively with the left child of the given root.
Call the function recursively with the right child of the given root.

Python Code for Invert Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        
        # Base condition
        if not root:
            return root
        
        #Swap left and right node
        root.left,root.right = root.right , root.left
        #Call left and right node recursively
        self.invertTree(root.left)
        self.invertTree(root.right)
        
        return root