Are Two Trees Identical

easy tree recursion

Problem

Two binary trees are identical when they have the same shape and the same value at every corresponding position. Decide whether the inputs are identical with one DFS that walks both at the same time.

Inputp = "1, 2, 3", q = "1, 2, 3"

Outputtrue

Trees use level-order notation; "_" means a missing child.

tree p (level-order)

tree q (level-order)

def is_same(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same(p.left, q.left) and is_same(p.right, q.right)

function isSame(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSame(p.left, q.left)
      && isSame(p.right, q.right);
}

class Solution {
    public boolean isSame(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;
        return isSame(p.left, q.left) && isSame(p.right, q.right);
    }
}

bool isSame(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    if (p->val != q->val) return false;
    return isSame(p->left, q->left)
        && isSame(p->right, q->right);
}

Time: O(n) Space: O(h) recursion