Logo
    Akhil Abraham
    Akhil Abraham
    0101 - Symmetric Tree
    0101 - Symmetric Tree

    0101 - Symmetric Tree

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/symmetric-tree/

    Solution 1 - Recursive Mirror Check

    Define a helper function that takes two nodes and checks if they are mirrors of each other. Two nodes are mirrors if both are None, or if their values are equal and the left child of one mirrors the right child of the other, and vice versa. Call the helper with root, root to check the full tree.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(h)SpaceComplexity: O(h)SpaceComplexity:O(h)

    Solution 2 - Iterative with Queue

    Use a queue to compare nodes level by level. Start by enqueuing the root twice. At each step, dequeue two nodes and compare them. If both are None, continue. If only one is None or their values differ, return False. Otherwise, enqueue the children in mirror order: left of first with right of second, and right of first with left of second.

    TimeComplexity:O(n)TimeComplexity: O(n)TimeComplexity:O(n)
    SpaceComplexity:O(n)SpaceComplexity: O(n)SpaceComplexity:O(n)
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    """ 0101.1 - Symmetric Tree - Solution 1 - Recursive Mirror Check """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        """Symmetric Tree Function"""

        def isMirror(t1: Optional[TreeNode], t2: Optional[TreeNode]) -> bool:
            if not t1 and not t2:
                return True
            if not t1 or not t2:
                return False
            return (
                t1.val == t2.val
                and isMirror(t1.left, t2.right)
                and isMirror(t1.right, t2.left)
            )

        return isMirror(root, root)


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1,2,2,3,4,4,3] -> True
    root1 = TreeNode(1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3))
    )
    print(Solution().isSymmetric(root1))  # True

    # [1,2,2,null,3,null,3] -> False
    root2 = TreeNode(1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3))
    )
    print(Solution().isSymmetric(root2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0101.2 - Symmetric Tree - Solution 2 - Iterative with Queue """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional
from collections import deque

#####################################################################################
# Classes
#####################################################################################
class TreeNode:
    """TreeNode Class"""

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


class Solution:
    """Solution Class"""

    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        """Symmetric Tree Function"""
        queue = deque([root, root])

        while queue:
            t1 = queue.popleft()
            t2 = queue.popleft()

            if not t1 and not t2:
                continue
            if not t1 or not t2:
                return False
            if t1.val != t2.val:
                return False

            queue.append(t1.left)
            queue.append(t2.right)
            queue.append(t1.right)
            queue.append(t2.left)

        return True


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # [1,2,2,3,4,4,3] -> True
    root1 = TreeNode(1,
        TreeNode(2, TreeNode(3), TreeNode(4)),
        TreeNode(2, TreeNode(4), TreeNode(3))
    )
    print(Solution().isSymmetric(root1))  # True

    # [1,2,2,null,3,null,3] -> False
    root2 = TreeNode(1,
        TreeNode(2, None, TreeNode(3)),
        TreeNode(2, None, TreeNode(3))
    )
    print(Solution().isSymmetric(root2))  # False


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()