100. Same Tree

Check out the problem description here.

Same Tree - LeetCode

Solution

Recursively traverse the tree. Here we check if the right subtree, right sub tree and the current node in the first tree is same as that of the second tree.

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        return (self.rec(p,q))
    
    def rec(self,p,q):
        if p==None and q==None:
            return True
        if(p==None or q==None):
            return False
        if p.val == q.val:
            return(self.rec(p.left,q.left) and self.isSameTree(p.right,q.right))

Time: O(N) -> N is the number of the nodes in first or second tree

Space: O(log(N)) that is the depth of tree, which is the auxiliary space for the stack calls.