< Back




100. Same Tree

We have the root of two binary trees, p and q. We have to determine if these two binary trees are
the same. We do this by using depth-first search to traverse both trees simultaneously. We compare
each node at each step of the search. If the nodes are not equal, we return False. If we reach the
end of the search and all nodes are equal, we return True.

The solution is as follows:


  class Solution:
      def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
          stack = [(p, q)]

          while stack:
              p, q = stack.pop()

              if not p and not q:
                  continue

              if not q or not p:
                  return False

              if p.val != q.val:
                  return False

              stack.append((p.right, q.right))
              stack.append((p.left, q.left))

          return True


_ Time Complexity:

  O(n) - We inspect all nodes in the binary tree.

_ Space Complexity:

  O(n) - We maintain a stack of nodes to explore.