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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Symmetric Tree

Number: 101

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Meta, Bloomberg, LinkedIn, Yandex, Apple, Adobe, Microsoft, TikTok, Comcast

Problem Description

Given the root of a binary tree, determine if the tree is a mirror of itself (i.e., symmetric around its center). In other words, check if the left subtree is a mirror reflection of the right subtree.

Key Insights

  • Use recursion (or iteration) to compare pairs of nodes.
  • For two trees (or two nodes) to be mirror images:
    • Their root values must be the same.
    • The left subtree of one must match the right subtree of the other.
    • The right subtree of one must match the left subtree of the other.
  • Alternatively, iterative approaches using a queue can be applied to compare the nodes in pairs.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, since we traverse each node once. Space Complexity: O(h) for recursive call stack (worst-case O(n) for a skewed tree) or O(n) for the iterative approach using a queue.

Solution

We solve the problem using recursion by defining a helper function that takes two nodes and checks if they are mirrors of each other. The helper function:

  1. Returns true if both nodes are null.
  2. Returns false if one node is null or if their values differ.
  3. Recursively compares the left child of the first node with the right child of the second node, and vice-versa. This method ensures each comparison verifies symmetry at every level. A similar logic can be applied iteratively by using a queue to compare pairs of nodes.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val          # current node's value
        self.left = left        # pointer to left child
        self.right = right      # pointer to right child

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        # Helper function to check mirror symmetry between two trees.
        def isMirror(t1: TreeNode, t2: TreeNode) -> bool:
            # Both nodes are null, so they are mirrors.
            if t1 is None and t2 is None:
                return True
            # If one is null or the values do not match, symmetry fails.
            if t1 is None or t2 is None or t1.val != t2.val:
                return False
            # Recursively check mirror symmetry for children:
            # t1's left with t2's right and t1's right with t2's left.
            return isMirror(t1.left, t2.right) and isMirror(t1.right, t2.left)
        
        # Start recursion comparing the tree with itself.
        return isMirror(root, root)
← Back to All Questions