Same Tree (Leetcode #100)

The "Same Tree" problem is a classic question that tests your understanding of binary tree structures and your ability to solve problems using recursion. In this post, we'll take a look at the problem, discuss a brute-force approach, provide hints, and share an efficient solution. Let's dive in!

Understanding the Problem Statement

The problem "Same Tree" asks whether two given binary trees are structurally identical and have identical node values.

In other words, given two binary trees, you need to determine if they are the same—meaning they have the same shape and each corresponding node contains the same value.

For example:

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

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

Brute Force Approach

A straightforward way to solve this problem is to perform level-order traversal (or breadth-first traversal) on both trees simultaneously and compare the nodes at every level. If at any point you find that a node in one tree does not match the corresponding node in the other, the trees are not the same.

However, using level-order traversal can be unnecessarily complex for this problem, as it requires additional data structures (e.g., queues) to hold nodes at each level. This brute-force approach often leads to higher memory usage, making it less efficient.

Hint to Solve the Problem Efficiently

Instead of using a brute-force traversal approach, consider a recursive solution. Since each node has only a left and right child, recursion can easily handle the comparison by navigating through both trees simultaneously. The recursion will check if both nodes are None, and if they aren’t, it will compare their values and proceed to their respective children.

Efficient Solution

Below is an efficient solution that uses recursion to solve the problem. We will determine if the given trees p and q are the same using a recursive approach, as shown in the provided code:

pythonCopy code# 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:
        # Base case: if both trees are empty
        if p == None and q == None:
            return True

        # Trees are not the same if either of them is empty or values are different
        if p == None or q == None or p.val != q.val:
            return False

        # Check recursively for left and right subtrees
        left_compare = self.isSameTree(p.left, q.left)
        right_compare = self.isSameTree(p.right, q.right)

        return left_compare and right_compare

In this solution:

• We start by handling the base case where both trees are empty (None). If both are empty, then they are considered identical.

• If one of the trees is empty or the values at the current nodes differ, we return False.

• Otherwise, we recursively check the left and right children of both trees.

• Finally, we return the combined result of the left and right subtree comparisons.

Time and Space Complexity

• Time Complexity: O(N)
  The time complexity is O(N) where N is the number of nodes in each tree. In the worst case, we need to visit every node in both trees to ensure they are identical.

• Space Complexity: O(H)
  The space complexity is O(H) where H is the height of the tree. This is due to the space taken up by the recursive call stack. In the worst case, for a skewed tree, this could be as high as O(N), while for a balanced tree, it will be O(log N).

Conclusion

The "Same Tree" problem is an excellent example of using recursion to solve problems with hierarchical structures like trees. While brute-force methods can be effective, leveraging recursion leads to a more intuitive and efficient solution.

If you're preparing for coding interviews, understanding this recursive approach will help you solve other similar problems involving binary trees.

Try coding this up and running it on a few different test cases to build your understanding. Keep practicing, and soon these recursive patterns will become second nature!