100. Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

This is a classic tree problem. If two trees $p, q$ are the same, then at the corresponding nodes:

1. The nodes have the same value.
2. They are structurally identical. What does “structurally identical” mean? There are two things we need to consider: that $p$ and $q$ are both either empty or non-empty, and that their descendants are the same. This is the recursive property that we must check.

def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
	if p is None and q is None:
		return True
	elif (p is None and q is not None) or (p is not None and q is None):
		return False
	elif p.val != q.val:
		return False
	else:
		return (self.isSameTree(p.left, q.left) 
				and self.isSameTree(p.right, q.right))

Time Complexity

Notice at every node there are only constant time operations. The algorithm recurses through every node, stopping only if the trees do not match or an empty node is reached. Therefore the algorithm has $\mathcal{O}(n)$ run time complexity.

Space Complexity

Since the algorithm in the worst case recurses through all nodes before returning, the space complexity is $\mathcal{O}(n)$, since each recursive call uses constant space.