algoadvance

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

For example:

    1
   / \
  2   2
 / \ / \
3  4 4  3

The above binary tree is symmetric.

However, the following binary tree is not:

    1
   / \
  2   2
   \   \
   3    3

Clarifying Questions

1. What type of values do the nodes contain?
   • The nodes contain integer values.
2. Can the tree be empty?
   • Yes, an empty tree is considered symmetric.
3. What is the definition of symmetry in the context of this problem?
   • A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
4. Is there a specific tree structure (like binary search tree or complete binary tree)?
   • No, the tree can be any binary tree structure.

Strategy

1. Recursive Approach:
   • Create a helper function to compare the left and right subtrees.
   • Base case: If both nodes are None, return True. If only one is None, return False.
   • Recursive case:
     • The values of the nodes should be equal.
     • The left subtree of the left node should be a mirror of the right subtree of the right node and vice versa.
2. Iterative Approach:
   • Use a queue to perform breadth-first search (BFS) to compare nodes level by level.
   • Enqueue the left and right children of the nodes in the required order to compare symmetry.

We’ll implement the recursive approach here for simplicity.

Code

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

def isSymmetric(root: TreeNode) -> bool:
    def isMirror(left: TreeNode, right: TreeNode) -> bool:
        if left is None and right is None:
            return True
        if left is None or right is None:
            return False
        return (left.val == right.val and 
                isMirror(left.left, right.right) and 
                isMirror(left.right, right.left))
    
    return isMirror(root.left, root.right) if root else True

# Example Usage:
# 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)
# print(isSymmetric(root))  # Output: True

Time Complexity

• Time Complexity: O(n), where n is the number of nodes in the tree. Each node is visited exactly once.

• Space Complexity: O(h), where h is the height of the tree. This is the space used by the recursion stack. In the worst case (skewed tree), the height h could be n.

This solution efficiently checks whether a binary tree is symmetric by leveraging a recursive helper function to compare the left and right subtrees for mirror properties.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?