Symmetric Tree easy

Problem Statement

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

Steps

1. Recursive Approach: We'll use a recursive function to check for symmetry. The core idea is that a tree is symmetric if the left subtree is a mirror image of the right subtree.

2. Base Cases:

   • If both left and right nodes are None, it means we've reached the end of a branch, and the sub-tree is symmetric (return True).
   • If only one of left or right is None, the tree is not symmetric (return False).
   • If the values of left and right nodes are different, the tree is not symmetric (return False).

3. Recursive Step: If the values are the same and neither node is None, recursively check if the left subtree's right child is a mirror of the right subtree's left child, and vice-versa. This mirrors the structure.

Explanation

The recursive function isSymmetric compares nodes in a mirrored fashion. It ensures that for each node on the left side, there's a corresponding node with the same value on the right side, and their subtrees are also mirrors of each other. The base cases handle scenarios where branches end, ensuring that the comparison stops correctly.

Code

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

def isSymmetric(root):
    """
    :type root: TreeNode
    :rtype: bool
    """

    def check(left, right):
        if not left and not right:
            return True
        if not left or not right:
            return False
        if left.val != right.val:
            return False
        return check(left.left, right.right) and check(left.right, right.left)

    return check(root.left, root.right)


#Example Usage
root = TreeNode(1, TreeNode(2, TreeNode(3), TreeNode(4)), TreeNode(2, TreeNode(4), TreeNode(3)))
print(isSymmetric(root)) #Output: True

root = TreeNode(1, TreeNode(2, None, TreeNode(3)), TreeNode(2, None, TreeNode(3)))
print(isSymmetric(root)) #Output: False

Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. We visit each node at most once.
• Space Complexity: O(H) in the worst case, where H is the height of the tree. This is due to the recursive call stack. In a balanced tree, H = log(N), and in a skewed tree, H = N.