Invert a Binary Tree

Consider a Binary Tree (T). The inversion of T is also a Binary tree (M) with left and right children of T swapped.

If you're curious to solve this problem before checking out the solution. Try it out in Leetcode 😉 .

You can find my solutions to other leetcode problems at https://github.com/Rage-ops/Leetcode-Solutions.

---

Solution

• We can solve this problem both iteratively and recursively.
• I'll be using the boilerplate code from leetcode to show both approaches. You can directly submit the solution and verify, once you understand how the algorithm works.

Recursive Approach

Let's just create an invert function that will take our original binary tree and return the inverted binary tree.

And the functionality of the invert function should be:

• Swap left and right child nodes of the current node.
• Call invert for the left child.
• Call invert for the right child.

This sounds so easy right ?. Yes, it is 😄. We can literally solve this problem recursively with these three lines of code.

# 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: TreeNode) -> TreeNode:
        self.helper(root)
        return root

    # recursive     
    def helper(self, node):
        if node:
            node.left, node.right = node.right, node.left
            self.helper(node.left)
            self.helper(node.right)

---

Iterative Approach

• Use BFS to explore the tree and swap left and right child for every node.

# 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
from queue import Queue
class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        return self.iterative_invert(root)

    def iterative_invert(self, root):
        if root:
            q = Queue()
            q.put(root)
            while q.qsize() > 0:
                node = q.get()
                node.left, node.right = node.right, node.left
                if node.left:
                    q.put(node.left)
                if node.right:
                    q.put(node.right)
        return root

---

Time Complexity: O(N) as we are visiting each node at once.

Space Complexity: O(N) since in the worst case, the queue will contain all nodes of the binary tree.

The time and space complexities are the same for both the recursive and iterative approaches. In the case of recursion, we can have n function calls placed in the stack at the same time in the worst-case scenario.

---