deepSWE.io

Symmetric Tree

TreesDFS / BFS

EasyLeetCode #101

15 min

Problem Statement

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

Example

Example 1:

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

Output: true

Solution 1: Recursive

The recursive approach checks for symmetry by comparing the left and right subtrees in a mirrored fashion.

Algorithm Steps

Create a helper function that takes two nodes as arguments.
If both nodes are null, they are symmetric.
If one node is null or their values are not equal, they are not symmetric.
Recursively call the helper function, comparing the left child of the first node with the right child of the second node, and vice versa.

Symmetric: true

Comparing left node 2 and right node 2.

Symmetric Tree Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        def is_mirror(t1, t2):
            if not t1 and not t2:
                return True
            if not t1 or not t2 or t1.val != t2.val:
                return False
            
            return is_mirror(t1.left, t2.right) and is_mirror(t1.right, t2.left)
            
        return is_mirror(root.left, root.right)

Solution 2: Iterative

The iterative approach uses a queue to compare the left and right subtrees level by level.

Algorithm Steps

Create a queue and add the left and right children of the root.
While the queue is not empty, dequeue two nodes.
If both nodes are null, continue.
If one node is null or their values are not equal, they are not symmetric.
Enqueue the children of the two nodes in a mirrored fashion.

Symmetric: true

Comparing left node 2 and right node 2.

Symmetric Tree Solution


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
            
        q = deque([root.left, root.right])
        
        while q:
            t1, t2 = q.popleft(), q.popleft()
            
            if not t1 and not t2:
                continue
            if not t1 or not t2 or t1.val != t2.val:
                return False
                
            q.append(t1.left)
            q.append(t2.right)
            q.append(t1.right)
            q.append(t2.left)
            
        return True