To solve the “Symmetric Binary Tree” problem, we can use a recursive approach to check if the left and right subtrees are mirror images of each other.

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

def is_symmetric(root: TreeNode) -> bool:
    def is_mirror(left: TreeNode, right: TreeNode) -> bool:
        # Base case: Both nodes are None, considered symmetric
        if not left and not right:
            return True
        # If one of the nodes is None and the other is not, not symmetric
        if not left or not right:
            return False
        # Check if values are equal and if subtrees are symmetric
        return left.val == right.val and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)

    # Check if the tree is symmetric starting from the root
    return is_mirror(root, root)

# Example usage:
#        1
#       / \
#      2   2
#     / \ / \
#    3  4 4  3
symmetric_tree = TreeNode(1, 
	                      TreeNode(2, 
	                      	       TreeNode(3), 
	                      	       TreeNode(4)
	                      	       ), 
	                      TreeNode(2, 
	                      	       TreeNode(4), 
	                      	       TreeNode(3)
	                      	       )
	                      )
result_symmetric = is_symmetric(symmetric_tree) 
print(result_symmetric)
assert result_symmetric is True

#        1
#       / \
#      2   2
#       \   \
#        3    3
non_symmetric_tree = TreeNode(1,
	                          TreeNode(2, 
	                          	       None, 
	                          	       TreeNode(3)
	                          	       ), 
	                          TreeNode(2, 
	                          	       None,
	                          	       TreeNode(3)
	                          	       )
	                          )
result_non_symmetric = is_symmetric(non_symmetric_tree)
print(result_non_symmetric)
assert result_non_symmetric is False

Explanation:

  • The is_symmetric function defines a helper function is_mirror that checks if two trees are mirrors of each other.
    • The base case checks if both nodes are None, which is considered symmetric.
    • If one of the nodes is None and the other is not, or if their values are not equal, the trees are not symmetric.
    • The function recursively checks if the left subtree of the left node is a mirror of the right subtree of the right node and vice versa.
  • The main function is_symmetric calls the helper function, starting from the root of the tree.

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 traversal.

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.