Symmetric Tree

Clarify the problem:

• The problem requires determining whether a binary tree is symmetric.
• We need to implement a function that takes the root of a binary tree as input and returns a boolean value indicating whether the tree is symmetric or not.

Analyze the problem:

• Input: The root of a binary tree.
• Output: A boolean value indicating whether the binary tree is symmetric or not.
• Constraints:
  • The number of nodes in the tree can be in the range [0, 1000].
  • Each node in the tree has a value in the range [-1000, 1000].
  • The tree can be an empty tree.

Design an algorithm:

• We can solve this problem recursively by checking whether the left and right subtrees are mirror images of each other.
• To check if two trees are mirrors, we can compare their roots' values and recursively compare the left subtree of the first tree with the right subtree of the second tree, and vice versa.
• If both subtrees are empty, they are mirror images.
• If one subtree is empty and the other is not, they are not mirror images.
• If both subtrees are non-empty, their roots' values must be equal, and the left subtree of the first tree should be a mirror image of the right subtree of the second tree, and the right subtree of the first tree should be a mirror image of the left subtree of the second tree.

Explain your approach:

• We will implement a recursive function called isSymmetric that takes the root of a binary tree as input.
• The function will check if the tree is symmetric by calling another recursive helper function called isMirror.
• The isMirror function takes two nodes as input and checks if they are mirror images of each other.
• If both nodes are None, they are mirror images and we return True.
• If one node is None and the other is not, they are not mirror images, so we return False.
• If both nodes are non-None, we compare their values. If they are not equal, they are not mirror images, so we return False.
• Finally, we recursively call the isMirror function for the left and right subtrees, passing the left subtree of the first node and the right subtree of the second node, and vice versa.
• If both recursive calls return True, it means both subtrees are mirror images, and we return True. Otherwise, we return False.

Write clean and readable code:

python

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

def isSymmetric(root):
    if root is None:
        return True
    return isMirror(root.left, root.right)

def isMirror(node1, node2):
    if node1 is None and node2 is None:
        return True
    if node1 is None or node2 is None:
        return False
    if node1.val != node2.val:
        return False
    return isMirror(node1.left, node2.right) and isMirror(node1.right, node2.left)

Test your code:

python

# Test case 1
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.left = TreeNode(3)
root.left.right = TreeNode(4)
root.right.left = TreeNode(4)
root.right.right = TreeNode(3)
# The tree is symmetric.
assert isSymmetric(root) == True

# Test case 2
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(2)
root.left.right = TreeNode(3)
root.right.right = TreeNode(3)
# The tree is not symmetric.
assert isSymmetric(root) == False

# Test case 3
root = None
# An empty tree is symmetric.
assert isSymmetric(root) == True

Optimize if necessary:

• The provided solution already has an efficient algorithm for checking the symmetry of a binary tree using recursive traversal.
• There is no further optimization possible for this problem.

Handle error cases:

• The given code assumes that the input root is a valid binary tree represented using the TreeNode class. If the input is not a valid binary tree or contains invalid values, it may result in unexpected behavior.

Discuss complexity analysis:

• The time complexity of the solution is O(n), where n is the number of nodes in the tree. We need to traverse each node once to check its symmetry.
• The space complexity is O(h), where h is the height of the tree. In the worst case, the space complexity is O(n) for a skewed tree, and in the best case, it is O(log n) for a balanced tree. The space is used for the recursive call stack.