Invert Binary Tree (Leetcode #226)

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

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

Answer

This answer can be done in many ways but I choose to do it via DFS or Depth First Search. DFS will go along one path as far as possible then back track and repeat the method.

To reverse a binary tree we can write out a function to reverse the binary tree and then using DFS to call it on their children.

        if not root:
            return root
        temp = root.left
        root.left = root.right
        root.right = temp

In this section, we are doing two things. First, we check if the tree is empty and if it is we can return it immediately. Second we are writing a code to swap the node of the binary tree. After we finish writing our function to swap the node now we can call DFS.

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

This code will keep going down the left path as far as possible and the backtrack to do the right path which will look something like

Combing everything our answer will be

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return root
        temp = root.left
        root.left = root.right
        root.right = temp

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

Time Complexity:
We are visiting each node ounce and the swaping time complexity is O(1). Hence O(1) * N = O(N) time complexity.

Space Complexity

This will depend on the balance of the tree since the space complexity is depends on the recursion stack.

1. If the tree is balanced then the recursion stack is O(logN)

2. If the tree is unbalanced the worst case stack is O(N)

Hence time complexity is in the best case O(logN) and worst case O(N)