To solve the “Invert Binary Tree” problem, we can use a recursive approach to swap the left and right children of each node.

Here’s the implementation:

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

def invert_tree(root: TreeNode) -> TreeNode:
    if not root:
        return None

    # Swap left and right children of the current node
    root.left, root.right = root.right, root.left

    # Recursively invert the left and right subtrees
    invert_tree(root.left)
    invert_tree(root.right)

    return root

# Example usage:
original_tree = TreeNode(4, 
	                     TreeNode(2, 
	                     	      TreeNode(1), 
	                     	      TreeNode(3)
	                     	      ), 
	                     TreeNode(7, 
	                     	      TreeNode(6), 
	                     	      TreeNode(9)
	                     	      )
	                     )

inverted_tree = invert_tree(original_tree)
# Inverted Binary Tree:
#        4
#       / \
#      7   2
#     / \ / \
#    9  6 3  1

# Verify the root node
assert inverted_tree.val == 4

# Verify level-2 nodes
assert inverted_tree.left.val == 7
assert inverted_tree.right.val == 2

# Verify level-3 nodes
assert inverted_tree.left.left.val == 9
assert inverted_tree.left.right.val == 6
assert inverted_tree.right.left.val == 3
assert inverted_tree.right.right.val == 1

Explanation:

  • The invert_tree function takes the root of a binary tree and recursively inverts it.
  • For each node, it swaps its left and right children using a simultaneous assignment.
  • The function then recursively calls itself on the left and right subtrees.
  • The base case is when the current node is None, in which case it returns None.
  • The final inverted tree is obtained by recursively applying these swaps.

Time Complexity:

The time complexity is O(N), where N is the number of nodes in the binary tree. We visit each node once during the inversion.

Space Complexity:

The space complexity is O(H), where H is the height of the binary tree. This is the maximum depth of the recursive call stack. In the worst case, the depth of the recursion is equal to the height of the tree.