# LevelOrderTraversal : Symmetric Tree

`1   / \  2   2 / \ / \3  4 4  3`
`1   / \  2   2   \   \   3    3`
`def isSymmetric(self, root: TreeNode) -> bool:        # seems like a level by level traversal, using a deque to store all children from left to right.        # we need to traverse the deque from front->mid and back->mid, at the same time and compare values at opposite end nodes.        # Also add the children of those nodes to the queue.        if not root or not (root.left or root.right):            return True                q = collections.deque()                if root.left and root.right:               q.append(root.left)            q.append(root.right)        else:            return False                while q:            length = len(q)                        for i in range(length//2):                node = q[i]                mirrornode = q[length -1 -i]                                # lets check the False conditions                if (node and not mirrornode) or (not node and mirrornode) or (node and mirrornode and node.val != mirrornode.val):                    return False                    break                                for _ in range(length):                        node = q.popleft()                if node:                    q.append(node.left)                    q.append(node.right)                i += 1                            return True`
• Space complexity : There is additional space required for the search queue. In the worst case, we have to insert O(n)O(n) nodes in the queue. Therefore, space complexity is O(n)O(n).

## Approach 1: Recursive

A tree is symmetric if the left subtree is a mirror reflection of the right subtree.

1. The right subtree of each tree is a mirror reflection of the left subtree of the other tree.
`class Solution:    def isSymmetric(self, root: TreeNode) -> bool:                def symmetric_subtrees(t1:TreeNode, t2:TreeNode) -> bool:            # both are None return True            if not t1 and not t2:                 return True                        # either one of them is True return False            if (t1 and not t2) or (not t1 and t2):                 return False                        # recursively check the right of the tree to equal the left of the 2nd tree            # and check the left of the tree to equal the right of the 2nd Tree            return t1.val == t2.val and symmetric_subtrees(t1.right, t2.left) and symmetric_subtrees(t1.left, t2.right)                # this is the mindboggling part of everything here.        return symmetric_subtrees(root, root)`
• Space complexity : The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(n)O(n). Therefore, space complexity due to recursive calls on the stack is O(n)O(n) in the worst case.

--

--