Invert Binary Tree

Introduction

The "Invert Binary Tree" problem involves flipping a binary tree around its center. Specifically, for each node in the tree, we swap its left and right children. This operation transforms the tree into a mirror image of itself.

This problem is a simple exercise in tree traversal and recursive algorithms. It is often used to test a developer's understanding of tree structures and recursion.

Problem Statement

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

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

The tree node structure is defined as above. The task is to invert the binary tree so that for every node, the left and right children are swapped.

Approach

The simplest and most intuitive approach to solve this problem is to use recursion. We can recursively invert each subtree of the binary tree and swap the left and right children of each node.

The steps for the recursive approach are as follows:

• If the current node is null, return null (base case).
• Recursively invert the left and right subtrees.
• Swap the left and right children of the current node.
• Return the current node (with its inverted children).

This approach ensures that we traverse all nodes in the tree and invert each subtree, ultimately achieving the mirror image of the original tree.

Algorithm

The algorithm follows these steps:

1. If the current node is null, return null.
2. Recursively call the invert function on the left and right subtrees.
3. Swap the left and right children of the current node.
4. Return the current node after swapping its children.

This algorithm ensures that every node is visited once, and its left and right children are swapped.

Example

Consider the following binary tree:

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

After inverting the binary tree, the resulting tree will be:

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

As we can see, the left and right children of each node have been swapped, resulting in the mirror image of the original tree.

Code Implementation

Below is the Python code to invert a binary tree using recursion:

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

def invertTree(root):
    # Base case: if the node is null, return null
    if not root:
        return None
    
    # Recursively invert the left and right subtrees
    left_inverted = invertTree(root.left)
    right_inverted = invertTree(root.right)
    
    # Swap the left and right children of the current node
    root.left = right_inverted
    root.right = left_inverted
    
    # Return the root node (with its inverted children)
    return root
        

In this code: - The `invertTree` function is called recursively on the left and right children of each node. - After inverting the left and right subtrees, the left and right children of the current node are swapped. - The root node, with its children swapped, is returned after the inversion.

Time Complexity

The time complexity of this solution is O(n), where n is the number of nodes in the binary tree. This is because we visit every node exactly once to swap its left and right children.

The space complexity is O(h), where h is the height of the tree, due to the recursive call stack. In the worst case (for an unbalanced tree), the height of the tree can be O(n), resulting in a space complexity of O(n). In the best case (for a balanced tree), the height will be O(log n), so the space complexity will be O(log n).

Optimized Approach

The current approach using recursion is already optimal in terms of time complexity. However, if needed, we can also solve this problem iteratively using a queue or stack for level-order traversal or pre-order traversal. This would avoid the overhead of recursion and would also yield a time complexity of O(n).

The recursive solution is simple and concise, making it a preferred choice for most problems like this one. In most cases, the recursion stack will not be a problem unless the tree is very deep and unbalanced.

Time Complexity (Optimized)

The time complexity remains O(n), where n is the number of nodes in the tree. The space complexity, in the case of an unbalanced tree, can be O(n), but for a balanced tree, it would be O(log n) due to the recursive call stack.

Conclusion

The "Invert Binary Tree" problem is a classic tree manipulation problem that can be efficiently solved using recursion. The time complexity of the solution is O(n), where n is the number of nodes, and the space complexity is O(h), where h is the height of the tree due to the recursion stack. This problem tests the ability to traverse and modify tree structures, and it is a great exercise in understanding binary trees and recursion.