# LevelOrderTraversal : Symmetric Tree

Iterative — Easy : https://leetcode.com/problems/symmetric-tree/

Recursive — Medium [ very important and intuitive]

Hint : 1. A Tree is symmetric to itself. So if you implement a function which accepts two trees to check for symmetry, you can start the first call of the function with symmetric(root, root).

**Problem Statement:**

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree `[1,2,2,3,4,4,3]`

is symmetric:

`1`

/ \

2 2

/ \ / \

3 4 4 3

But the following `[1,2,2,null,3,null,3]`

is not:

`1`

/ \

2 2

\ \

3 3

**Follow up:** Solve it both recursively and iteratively.

Code:

Iterative:

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

**Complexity Analysis**

- Time complexity : O(n)
*O*(*n*). Because we traverse the entire input tree once, the total run time is O(n)*O*(*n*), where n*n*is the total number of nodes in the tree. - 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*).

**Recursive:**

## Approach 1: Recursive

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

Therefore, the question is: when are two trees a mirror reflection of each other?

Two trees are a mirror reflection of each other if:

- Their two roots have the same value.
- The right subtree of each tree is a mirror reflection of the left subtree of the other tree.

This is like a person looking at a mirror. The reflection in the mirror has the same head, but the reflection’s right arm corresponds to the actual person’s left arm, and vice versa.

The explanation above translates naturally to a recursive function as follows.

`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)

Runtime: 32 ms, faster than 80.82% of Python3 online submissions for Symmetric Tree.

Memory Usage: 14.3 MB, less than 81.57% of Python3 online submissions forSymmetric Tree.

- Time complexity : O(n)
*O*(*n*). Because we traverse the entire input tree once, the total run time is O(n)*O*(*n*), where n*n*is the total number of nodes in the tree. - 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.

Next to Solve: