100-same-tree.py

"""
Problem Link: https://leetcode.com/problems/same-tree/description/

Given two binary trees, 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:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]
Output: true

Example 2:
Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]
Output: false

Example 3:
Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]
Output: false
"""
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None


# Time Complexity: O(n), n -> total no of nodes
# Space Complexity: O(log(N)) in the best case of completely balanced tree and 
# O(N) in the worst case of completely unbalanced tree.
class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
          return True
        elif not p or not q:
          return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

    def isSameTree_iterative(self, p: TreeNode, q: TreeNode) -> bool:
      stack = [(p, q)]
      while stack:
          node1, node2 = stack.pop()
          if not node1 and not node2:
              continue
          elif not node1 or not node2:
              return False
          if node1.val != node2.val:
              return False
          stack.append((node1.right, node2.right))
          stack.append((node1.left, node2.left))
      return True