Symmetric Tree Check

Determine if a binary tree is a mirror of itself around its center.

binary-tree recursion mirror

A binary tree is symmetric if its left and right subtrees are mirror images of each other. The TreeNode class is defined as:

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

Implement the function `is_symmetric(root: TreeNode | None) -> bool` that returns `True` if the tree is symmetric, `False` otherwise. An empty tree (root is `None`) is symmetric. The tree values are integers. Symmetry is structural and value-based; for two nodes to be mirrors, their values must be equal and their children must mirror each other appropriately (left of one mirrors right of the other). The grader will pass TreeNode objects, not dictionaries, to your function.

Constraints

- The number of nodes in the tree is in [0, 1000].
- Each node's value is an integer in [-1000, 1000].
- The tree is a valid binary tree (each node has at most two children).
- Time complexity should be O(n), where n is the number of nodes. Space complexity O(h) for recursion stack, h being tree height.

Example

>>> root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
>>> is_symmetric(root)
True
>>> root2 = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
>>> is_symmetric(root2)
False
>>> is_symmetric(None)
True

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Two trees are mirrors if their roots have equal values and the left of the first is a mirror of the right of the second.

Write a helper function that checks if two nodes are mirrors of each other.

The base case is when both nodes are None, return True; if exactly one is None, return False.

For the whole tree, check if root.left and root.right are mirrors. Also handle the empty root.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.