101. Symmetric Tree

Question

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

Solution 1: Recursive (DFS)

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        return self.dfs(root.left, root.right)
    
    def dfs(self, lftNode, rhtNode):
        if (not lftNode) and (not rhtNode):
            return True
        elif (not lftNode) or (not rhtNode):
            return False
        elif lftNode.val != rhtNode.val:
            return False
        # lftNode.val == rhtNode.val, compare the children
        else:
            return self.dfs(lftNode.left, rhtNode.right) and self.dfs(lftNode.right, rhtNode.left)

Time Complexity: O(N)
Space Complexity: O(N)

Solution 2: Iterative + Queue (BFS)

import queue

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        
        Q = queue.Queue()
        Q.put(root.left)
        Q.put(root.right)
        while not Q.empty():
            nodeLft = Q.get()
            nodeRht = Q.get()
            
            if not nodeLft and not nodeRht:
                continue
            elif not nodeLft or not nodeRht:
                return False
            elif nodeLft.val != nodeRht.val:
                return False
            else:
                Q.put(nodeLft.left)
                Q.put(nodeRht.right)
                Q.put(nodeLft.right)
                Q.put(nodeRht.left)
            
        return True

Time Complexity: O(N)
Space Complexity: O(N)

Solution 3: Iterative + Stack (BFS)

Time Complexity: O(N)
Space Complexity: O(N)

Reference

https://leetcode.com/problems/symmetric-tree/discuss/33054/Recursive-and-non-recursive-solutions-in-Java