Check if two trees are the same

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

     1               |             1
   /   \             |           /   \
  2     3            |          2     3

The above trees are the same as the structure is identical and nodes have the same value.

     1               |             1
   /   \             |           /   \
  2     1            |          1     2

The above trees are not the same because nodes don't have the same value.

If you're curious to solve this problem before checking out the solution. Try it out in Leetcode 😉 .

You can find my solutions to other leetcode problems at https://github.com/harsha-sam/Leetcode-Solutions.

---

Solution

I'll be using the boilerplate code from leetcode. You can directly submit the solution and verify, once you understand how the algorithm works.

• Depth-first search both trees at the same time and return false if the structure is not identical or if the node values don't match.

# 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:
        return self.helper(p, q)

    def helper(self, node1, node2):
        # returns false if structure is not identical
        if node1 and not node2 or node2 and not node1:
            return False
        elif node1 and node2:
            if not self.helper(node1.left, node2.left):
                return False
            if node1.val != node2.val:
                return False
            if not self.helper(node1.right, node2.right):
                return False
        return True

Time Complexity: O(N)
Space Complexity: O(tree height)