Invert Binary Tree

Given the root of a binary tree, invert the tree by swapping the left and right children of each node.

Function Signature:

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:
    """
    Invert a binary tree.

    Parameters:
    - root: The root of the binary tree.

    Returns:
    - TreeNode: The root of the inverted binary tree.
    """
    # Your code here

Example:

# Example Binary Tree:
#        4
#       / \
#      2   7
#     / \ / \
#    1  3 6  9
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

Note:

• The given binary tree is not necessarily a binary search tree.
• All node values are unique.

Instructions:

• Write the invert_tree function to solve the problem.
• Implement your solution in Python.
• Provide clear comments in your code.
• Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊