# Recursive and non-recursive solutions in Python

• Recursive one:

``````  class Solution:
# @param root, a tree node
# @return a boolean
def isSymmetric(self, root):
# a new recursive function to check if two tree are symetric
def isMirror(root1,root2):
# they all could be Null to be symetric
if not root1 and not root2:
return True
# if they are not Null, they must carry the same value
elif (root1 and root2) and root1.val==root2.val:
# recursively call itself
return isMirror(root1.left,root2.right) and isMirror(root1.right, root2.left)
else:
return False
if not root:
return True
return isMirror(root.left, root.right)
``````

Non-recursive one:

``````class Solution:
# @param root, a tree node
# @return a boolean
def isSymmetric(self, root):
if not root :
return True
queue=[[root.left,root.right]] # use a queue to store nodes. Each element in the queue is a pair of nodes. They are supposed to carry the same value. Ortherwise, the tree is not symetric
while queue:
pair=queue.pop(0)
if not (pair[0] or pair[1]):
# if current pair are empty, do nothing
continue
elif (pair[0] and pair[1]) and pair[0].val==pair[1].val:
# if current pair carry the same value, push the their children pairs into the queue
queue.append([pair[0].left,pair[1].right])
queue.append([pair[0].right,pair[1].left])
else:
return False
# if all pairs pass the evaluation, the tree is symmetric
return True
``````

• Here the "queue" variable is actually a stack.

• Hi @sheehan,

Thanks for the comments. Actually the "queue" is a queue. I use queue.pop(0) to pop the first element in the list instead of the newly appended element. Thus it is a queue.

• Sorry, my Implementation use "pop()" not "pop(0)", so I ignored the zero. Use python list as a queue has performance problem that every time pop a element for top of a python list, the runtime would have to move all elements after first one one step ahead. This has a O(n) time complexity.

• https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt Here is a summary of most python function time complexity.

• Thank you @sheehan for sharing. It's of great help to me. Though pop(0) will have O(n) complexity, all test cases seem to be fine with my submission. Do you mind to share your implementation with stack?

• This basically is similar to your code with small optimization

``````class Solution:

def check_symmetry(self, node1, node2):

if not node1 and not node2:
return True
elif not node1 or not node2:
return False

return (node1.val == node2.val and
self.check_symmetry(node1.left, node2.right) and
self.check_symmetry(node1.right, node2.left))
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.