We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Symmetric Tree

Difficulty: Easy

Problem Description

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

Key Insights

  • A tree is symmetric if the left subtree is a mirror reflection of the right subtree.
  • Both subtrees must have the same structure and values at corresponding positions.
  • The recursive approach involves checking nodes in pairs, while the iterative approach can utilize a queue for level-order traversal.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we may need to visit each node once. Space Complexity: O(h) - where h is the height of the tree, due to the stack space used in recursion or the queue space in iteration.

Solution

To determine if a binary tree is symmetric, we can use both recursive and iterative approaches.

  1. Recursive Approach: We define a helper function that checks if two nodes are mirrors of each other. This function checks:

    • If both nodes are null, they are symmetric.
    • If one node is null and the other is not, they are not symmetric.
    • The values of the two nodes must be equal, and their children must also be mirrors of each other.

  2. Iterative Approach: We can use a queue to perform a level-order traversal. We enqueue pairs of nodes and check:

    • If both nodes are null, continue to the next pair.
    • If one node is null and the other is not, the tree is not symmetric.
    • The values of the nodes must match, and we enqueue their children in the correct order to maintain symmetry.

Code Solutions

def isSymmetric(root):
    if not root:
        return True
    
    def isMirror(node1, node2):
        if not node1 and not node2:
            return True
        if not node1 or not node2:
            return False
        return (node1.val == node2.val and
                isMirror(node1.right, node2.left) and
                isMirror(node1.left, node2.right))
    
    return isMirror(root.left, root.right)
← Back to All Questions