100: Same Tree#

Difficulty: Easy

Link to Problem: To see the Same Tree problem on LeetCode, click here!

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

  1. The number of nodes in both trees is in the range [0, 100].

  2. \(-10^4\) <= Node.val <= \(10^4\)

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

def isSameTree(p, q):
    # Base case: If both p and q are None, the trees are the same.
    if not p and not q:
        return True
    
    # Base case: If either p or q is None (but not both), the trees are different.
    if not p or not q:
        return False
    
    # Check if the values of the current nodes (p.val and q.val) are equal.
    if p.val != q.val:
        return False
    
    # Recursively check the left and right subtrees of p and q.
    # If both subtrees are the same, the entire trees are the same.
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

In this code, we define a TreeNode class to represent binary tree nodes and a isSameTree function to check if two binary trees are the same. The function uses recursive traversal to compare the trees’ structures and values.

  1. We start by defining a TreeNode class, which represents a node in a binary tree. Each node has a val (the node’s value), a left child, and a right child. This class will help us create and work with binary trees.

  2. Next, we define the isSameTree function, which checks if two binary trees (p and q) are the same.

    • The base case for the recursion is when both p and q are None. In this case, they are considered the same, so we return True.

    • If either p or q is None (but not both), they cannot be the same, so we return False.

    • If the values of the current nodes p.val and q.val are not equal, we return False because the trees cannot be the same.

    • Finally, we recursively check the left and right subtrees of p and q to see if they are the same.

Test cases#

### Example 1

#Input: `p = [1,2,3]`, `q = [1,2,3]`

p1 = TreeNode(1, TreeNode(2), TreeNode(3))
q1 = TreeNode(1, TreeNode(2), TreeNode(3))
print(isSameTree(p1, q1)) 

True

### Example 2

#Input: `p = [1,2]`, `q = [1,null,2]`

p2 = TreeNode(1, TreeNode(2), None)
q2 = TreeNode(1, None, TreeNode(2))
print(isSameTree(p2, q2))

False

### Example 3

#Input: p = [1,2,1], q = [1,1,2]

p3 = TreeNode(1, TreeNode(2), TreeNode(1))
q3 = TreeNode(1, TreeNode(1), TreeNode(2))
print(isSameTree(p3, q3))

False

Time and Space Complexity Analysis#

Time Complexity

The time complexity of the isSameTree function can be analyzed as follows:

In the worst case, the function needs to visit every node in both trees once to determine if they are the same. Since each node is visited exactly once, the time complexity is \(O(n)\), where \(n\) is the total number of nodes in the input trees.

Space Complexity The space complexity of the isSameTree function can be analyzed as follows:

The space used by the function’s call stack during recursion is proportional to the maximum depth of the binary trees. In the worst case, when the trees are completely unbalanced (all nodes form a single branch), the maximum depth will be \(n\), where \(n\) is the total number of nodes in the input trees. Therefore, the space complexity is \(O(n)\) due to the recursive call stack. In addition to the call stack, there is a small constant amount of space used for variables and comparisons within each recursive call, but this space is not significant in terms of the overall space complexity.

In summary:

  • Time Complexity: \(O(n)\) where \(n\) is the total number of nodes in the input trees.

  • Space Complexity: \(O(n)\) due to the recursive call stack.