# A recursive solution to symmetirc tree

I tried to solve a symmetric tree problem

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


Note: Bonus points if you could solve it both recursively and iteratively.

My solution with recursion

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def isSymmetric(self, root):
if not root: return True #None is symmetic
return self.isMirror(root.left, root.right)

def isMirror(self, l, r):
if not l and not r: return True #base case 1
if not l or not r: return False #base case 2
if l.val != r.val: return False #base case 3
#recur case
left = self.isMirror(l.left, r.right)
right = self.isMirror(l.right, r.left)
return left and right


I assumed it as a decent solution to this problem but get a low score

Runtime: 32 ms, faster than 24.42% of Python online submissions for Symmetric Tree. Memory Usage: 12.2 MB, less than 5.08% of Python online submissions for Symmetric Tree.

How could improve the my solution?

• You present input data both as a list and as a tree. Which one is the actual input form? If it is a list of integers, possibly you could do a recursive analysis just on that list and save the time needed for constructing a tree of linked TreeNode objects? – CiaPan Apr 1 '19 at 11:33
• You 'accepted' my answer, which should confirm my modification is correct and resolves your problem. If so, do you mind to share the scores your modified algorithm achieves? – CiaPan Apr 1 '19 at 12:46
• Where are you submitting these answers to get rankings like this? – Shawson Apr 1 '19 at 13:16
• @Shawson Possibly it's Geeks for geeks? Or may be the LeetCode? – CiaPan Apr 1 '19 at 17:37

Possibly the most obvious part is here

    left = self.isMirror(l.left, r.right)
right = self.isMirror(l.right, r.left)
return left and right


there's no need to perform the second test if the first one returns False:

    if not self.isMirror(l.left, r.right): return False
if not self.isMirror(l.right, r.left): return False

return True


Appart from the optimization provided by @CiaPan, you could try using an inner function to reduce the need for attributes lookups and accelerate symbols resolution speed:

class Solution(object):
def isSymmetric(self, root):
if root is None:
return True

def isMirror(left, right):
if left is None and right is None:
return True
elif left is None or right is None:
return False
elif left.val != right.val:
return False
else:
return isMirror(left.left, right.right) and isMirror(left.right, right.left)

return isMirror(root.left, root.right)


Alternatively, you could try the iterative approach which is usually implemented using a deque to perform a breadth first search:

from collections import deque

class Solution(object):
def isSymmetric(self, root):
if root is None:
return True

rights = deque([root.right])
lefts = deque([root.left])
while lefts:
left = lefts.popleft()
right = right.popleft()
if left is None and right is None:
pass
elif left is None or right is None:
return False
elif left.val != right.val:
return False
else:
lefts.append(left.left)
lefts.append(left.right)
rights.append(right.right)
rights.append(right.left)

return True

• As it often happens, optimization needs to fit the actual data characteristics. With BSF one should remember that a full binary tree has $2^d$ items at the level of depth $d$ , so the queue can grow much faster (and larger) than a stack. On the other hand with DSF a stack can grow huge if the tree is degenerated to a list. – CiaPan Apr 9 '19 at 10:14