# Python Accepted Solution

• ``````class Solution:
# @param p, a tree node
# @param q, a tree node
# @return a boolean
def isSameTree(self, p, q):
if p == None and q == None:
return True
elif p and q :
return p.val == q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
else :
return False
``````

what's the complexity of this solution?

• Starting from the root we have recursion stack as follows:
O(1) + O(2) + O(4) .. so forth for (1 + log N) times

However, considering no reduction in input size. I would estimate O(N)

We would need data with various input sizes to verify this claim via time versus input graph.

• This post is deleted!

• [AC 85ms] Once find two sub-trees not equal, return False before enter next recursion.

``````class Solution:
# @param p, a tree node
# @param q, a tree node
# @return a boolean
def isSameTree(self, p, q):
if p == None and q == None:
return True
elif p == None or q == None:
return False
elif p.val != q.val:
return False

return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)``````

• I consider the time complexity is O(N) since the algorithm goes through each nodes of the tree.

{

``````class Solution:
def isSameTree(self, p, q):

if p == None and q == None:
return True
elif (p != None and q != None):
if p.val != q.val:
return False
if self.isSameTree(p.left, q.left) == False:
return False
else:
return self.isSameTree(p.right, q.right)
else:
return False
``````

}

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