@pankit Yes, I think this is the best way to do it -- just trace DFS in both directions simultaneously, and recursion is a perfect fit here as well. No need to allocate any more memory than what is involved in the recursion itself.
I did it in exactly the same way, except for using "a" and "b" instead of "p" and "q", and I named the recursive routine "mirrorMatch()" -- interviewers should get positive impressions from meaningful names.
Just to provide another optional python solution, for those who do inroder traversal but can not make it right.
Here, we need to encode the left and right information with the traversal.
In the solution below, I multiply by -1 for left, +1 for right.
And their inorder traversal shall be reversed.
def isSymmetric(self, root):
if not root:
left = self.inorder(root.left, -1) # left using -1
right = self.inorder(root.right, 1) # right using +1
if len(left) != len(right):
for i,_ in enumerate(left):
if left[i] + right[len(left)-1-i]:
def inorder(self, node, sign):
if not node:
ret = 
ret = self.inorder(node.left, -1)
ret.append(node.val * sign)
ret += self.inorder(node.right, 1)