Leetcode 100 - Same Tree

Problem

Leetcode 100 - Same Tree

Example:

Input: p = [1,2,3], q = [1,2,3]
Output: true

Input: p = [1,2], q = [1,null,2]
Output: false

Input: p = [1,2,1], q = [1,1,2]
Output: false

Approach

This problem can be solved by checking whether the left and right subtrees of each node are the same. We can use a recursive function to check whether the left and right subtrees of each node are the same.

Base case:

• If both nodes are null, return True
• If one of the nodes is null, return False
• If the values of the two nodes are different, return False

Recursive case:

• Recursively call the function on the left and right subtrees of the current node

Visualization of the approach:

    1       1
   / \     / \
  2   3   2   3

p: 1 == 1, True
p.left: 2 == 2, True
p.right: 3 == 3, True

Thus, the tree is the same, return True.

Here is the implementation of the approach:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # Base case (1): if both nodes are null, return True
        if not p and not q: return True

        # Base case (2): if one of the nodes is null or the values of the two nodes are different, return False
        if not (p and q and p.val == q.val): return False
        
        # Recursive case: recursively call the function on the left and right subtrees of the current node
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time Complexity and Space Complexity

The time complexity of this approach is $O(n)$ since we are visiting each node once.

The space complexity is $O(n)$ since we are using a recursive function.