Problem Statement

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

Link To the Problem

Intuition

A binary tree is a tree where each node has at most 2 children, commonly referred to as left and right. Inverting a binary tree means swapping the left and right subtrees of every node.

Approach

We can solve this problem recursively or iteratively:

• Recursive Approach (DFS):

  • If the current node is None, return None.

  • Swap the left and right children recursively:

  • Set the left child to the result of inverting the original right subtree.

  • Set the right child to the result of inverting the original left subtree.

  • Return the current node.

• Iterative Approach (BFS):

  • Use a queue to perform level-order traversal.

  • For each node in the queue, swap its left and right children.

  • Add non-null children to the queue for further processing.

Complexity

• Time complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.
• Space complexity:
  • Recursive approach: O(h) due to the recursion stack, where h is the height of the tree.
  • Iterative approach: O(n) in the worst case for the queue.

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:

    # Recursive Implementation (DFS)
    def invert_tree_recursively(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root :
            return

        # swap the nodes in place
        root.left,root.right = self.invert_tree_recursively(root.right),self.invert_tree_recursively(root.left)

        return root

    # Iterative Implementation (BFS)
     def invert_tree_iteratively(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        queue = deque([root])

        while queue:
            node = queue.popleft()

            # swap the nodes in place
            node.left, node.right = node.right, node.left

            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        return root