Question Description

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

Example 1:

Input: root = [1,2,2,3,4,4,3] Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3] Output: false

Constraints:

The number of nodes in the tree is in the range [ [1, 1000] ]. -100 <= Node.val <= 100

Follow up: Could you solve it both recursively and iteratively?

problem link solution video link

Thought Process

  • we need to go through the tree
  • traversal order?
    • we want to compare node value symetric in one level
    • [!NOTE] we are not just compare the left and right node, we want the symetry, so we need to compare the inner nodes pair and outer nodes pair

Code

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        # first we need to check the base case, if there's no tree,
        # then no point to compare
        if not root.left and not root.right: return True
        if not root.left or not root.right: return False

        # then we call our compare helper function to help deal with subtree
        return self.compare(root.left, root.right)

    def compare(self, left: Optional[TreeNode], right: Optional[TreeNode]) -> bool:

        
        if not left and not right: return True

        # this part will performming the "symetric" compare to see if they have equal values:
        # by definition, we will compare the inner child, which will be
        #   - right child of the left subtree root
        #   - left child of the right subtree root
        if (not left and right) or (not right and left): return False

        #   - left child of the left subtree root
        #   - right child of the right subtree root
        if left.val != right.val: return False

        # then we recursively comparing the symetric tree: left's left subtree and right's right subtree,
        # left's right subtree and right's left subtree
        return self.compare(left.left, right.right) and self.compare(left.right, right.left)

Time/Space Complexity

Time: \( O(d) \) where \( d \) is the depth of the tree

Space: \( O(n) \) where \( n \) is number of elements in the tree

This question is similar way to solve level order traversal