LeetCode #100: Same Tree

LeetCode Solutions

https://leetcode.com/problems/same-tree/

This problem requires us to check whether two given binary trees are identical or not. In other words, we need to check if they have the same structure and each corresponding node has the same value.

To solve this problem, we can use a recursive approach where we compare the root node of both trees, then recursively compare the left and right sub-trees until we reach the leaf nodes. Here are the steps to solve this problem:

  1. Define a recursive function that takes in two tree nodes as parameters.
  2. Check if both tree nodes are None, which means we have reached the leaf nodes and return True.
  3. Check if one of the tree nodes is None and the other is not. In this case, the trees are not identical, and we return False.
  4. Check if the values of the current nodes are the same. If not, return False.
  5. Recursively call the function with the left sub-trees of both nodes.
  6. Recursively call the function with the right sub-trees of both nodes.
  7. If all comparisons are successful, return True.

Here’s the Python code that implements the above algorithm:

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        # If both nodes are None, they are identical
        if not p and not q:
            return True
        
        # If one node is None and the other is not, they are not identical
        if not p or not q:
            return False
        
        # If the values of the nodes are different, they are not identical
        if p.val != q.val:
            return False
        
        # Recursively check the left and right sub-trees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time Complexity: In the worst case, we may have to visit every node of both trees, so the time complexity is O(n), where n is the number of nodes in the tree.

Space Complexity: The space complexity is O(h), where h is the height of the tree, which represents the maximum number of function calls on the call stack at any given time. In the worst case, the height of the tree can be O(n), which makes the space complexity O(n).