100. Same Tree

Approach: Recursive DFS

Two trees are the same if their roots have equal values and their left and right subtrees are respectively the same.

Algorithm:

1. Base case: If both nodes are None, return True.
2. If one is None and the other is not, return False.
3. If both nodes exist, check if their values are equal.
4. Recursively check their left and right subtrees.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True

        if not p or not q or p.val != q.val:
            return False

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

• Time: $O(n)$ — where $n$ is the number of nodes in the tree.
• Space: $O(h)$ — the maximum depth of the tree.

For the recursive solution, the space complexity is O(h) because of the call stack. When traversing down the tree, each recursive call is placed on the call stack until a leaf is reached.

Last updated on