A recursive solution to symmetirc tree

Question

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?

Answer 1

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

Answer 2

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