// recursive solution: time complexity: O(n) | space complexity: O(h) where h is height of tree (recursion stack)
var isSameTree = function (p, q) {
  if (!p && !q) {
    return true;
  }
  if (!p || !q || p.val !== q.val) {
    return false;
  }
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};