Same Tree

Clarify the problem:

• The problem requires checking if two binary trees are the same or not.
• We need to implement a function that takes two binary tree nodes as input and returns true if the trees are the same, and false otherwise.

Analyze the problem:

• Input: Two binary tree nodes.
• Output: Boolean value indicating whether the trees are the same.
• Constraints: None specified.

Design an algorithm:

• We can solve this problem using a recursive approach.
• If both nodes are None, return True.
• If only one of the nodes is None, return False.
• If the values of the nodes are different, return False.
• Recursively check if the left subtree of both nodes is the same and if the right subtree of both nodes is the same.
• Return the logical AND of the above conditions.

Explain your approach:

• We will implement a function called isSameTree that takes two binary tree nodes as input.
• If both nodes are None, return True.
• If only one of the nodes is None, return False.
• If the values of the nodes are different, return False.
• Recursively check if the left subtree of both nodes is the same and if the right subtree of both nodes is the same.
• Return the logical AND of the above conditions.

Write clean and readable code:

python

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def isSameTree(p, q):
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    if p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

Test your code:

python

# Test case 1
# Tree 1:     1         Tree 2:     1
#           / \                    / \
#          2   3                  2   3
# The trees are the same.
assert isSameTree(
    TreeNode(1, TreeNode(2), TreeNode(3)),
    TreeNode(1, TreeNode(2), TreeNode(3))
) == True

# Test case 2
# Tree 1:     1         Tree 2:     1
#           / \                    / \
#          2   1                  1   2
# The trees are not the same.
assert isSameTree(
    TreeNode(1, TreeNode(2), TreeNode(1)),
    TreeNode(1, TreeNode(1), TreeNode(2))
) == False

# Test case 3
# Tree 1:     1         Tree 2:     1
#           / \                    / \
#          2   3                  2   4
# The trees are not the same.
assert isSameTree(
    TreeNode(1, TreeNode(2), TreeNode(3)),
    TreeNode(1, TreeNode(2), TreeNode(4))
) == False

Optimize if necessary:

• The provided solution has a time complexity of O(min(N, M)), where N and M are the numbers of nodes in the two trees being compared.
• The space complexity is O(min(H1, H2)), where H1 and H2 are the heights of the two trees being compared.

Handle error cases:

• The given code assumes that the input p and q are valid binary tree nodes. If either p or q is invalid, the behavior is undefined.

Discuss complexity analysis:

• The time complexity of the solution is O(min(N, M)), where N and M are the numbers of nodes in the two trees being compared.
• The space complexity is O(min(H1, H2)), where H1 and H2 are the heights of the two trees being compared.