[Problem Solving] Invert a Binary Tree

We are given a binary tree as shown below.

Let’s observe the given tree and compare it with the output. What do we notice?

The left child of a node becomes the right child and vice versa. So we start at the root node and invert the left and right children.

     1
   /   \
  2     3

becomes

     1
   /   \
  3     2

We then invert the left and right sub-trees starting at each of those children. This leads to a naturally recursive approach.

     1
   /   \
  3     2
 / \   / \
6   7 4   5

becomes

     1
   /   \
  3     2
 / \   / \
7   6 5   4

An intuitive way to solve most tree problems is to use recursion. Now we have to decide a few things before coding.

Base case:

Here, the base case would be a NULL node. We simply return at that point since there are no nodes left to invert.

Recursive strategy:

Our recursive strategy involves the following steps.

• Invert the left and right child of current node
• Recursive call to invert the left sub-tree starting at the left child
• Recursive call to invert the right sub-tree starting at the right child

Time Complexity: We will end up visiting each node in the tree, so the time complexity will be O(N) where N is the number of nodes in the tree.

Space Complexity: In recursion problems, an internal stack is used to temporarily hold elements, so the space complexity will be O(H) where H is the height of the tree. This is because as we recurse over left and right sub-trees, the function calls will go as deep as the tree height. In the worst case, H -> N, so the overall space complexity will be O(N) where N is the number of nodes in the tree.

Code for the above solution:

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

def invertTree(self, root: TreeNode) -> TreeNode:

    def invertTreeHelper(root):

        if not root:
            return

        root.left, root.right = root.right, root.left
        invertTreeHelper(root.left)
        invertTreeHelper(root.right)

    invertTreeHelper(root)
    return root

Testing:

These are some of the cases that are good to test for tree problems.

• Given test case: [1,2,3,4,5,6,7]
• Empty tree: []
• No children: [1]
• No right child: [1, 2]
• Right skewed tree: [1,null,2,null,3,null,4,null,5,null,6,null,7]
• Left skewed tree: [1,2,null,3,null,4,null,5,null,6,null,7]

Want to try to solve this problem? https://leetcode.com/problems/invert-binary-tree/

Hope you learnt how to invert a binary tree. Have a great day!