algoadvance

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.

Example 1:

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

Example 2:

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

Example 3:

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

Clarifying Questions

  1. What type of data structures can be used for the binary tree?
    • The binary tree is represented using TreeNode class provided by LeetCode.
  2. What should be returned if both trees are empty?
    • If both trees are empty, they should be considered the same, and the function should return true.
  3. What if one tree is empty and the other is not?
    • If one tree is empty and the other is not, they should be considered not the same, and the function should return false.

Strategy

To determine if two binary trees are the same, we’ll follow these steps recursively:

  1. Base Case: If both nodes are null, then the trees are the same up to this part.
  2. Base Case: If one node is null and the other node is not, then the trees are not the same.
  3. Value Check: If the current nodes’ values are different, then the trees are not the same.
  4. Recursive Check: Recursively check the left subtrees and right subtrees.

The recursion will ensure that we check each node’s value and structure recursively.

Code

Here’s how we can implement the above strategy in Python:

# 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: TreeNode, q: TreeNode) -> bool:
        # Base cases
        if not p and not q:
            return True
        if not p or not q:
            return False
        
        # Value comparison
        if p.val != q.val:
            return False
        
        # Recursively check left and right subtrees
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

Time Complexity

The time complexity for this solution is (O(N)), where (N) is the number of nodes in the tree. This is because we have to check each node exactly once.

Space Complexity

The space complexity is (O(H)), where (H) is the height of the tree. This represents the space used by the recursion stack. In the worst case (unbalanced tree), this could go up to (O(N)). In the best case (completely balanced tree), it would be (O(\log N)).

Try our interview co-pilot at AlgoAdvance.com