# Same Tree

- **Canonical ID**: `same-tree`
- **Canonical URL**: https://dsacheatsheet.com/problems/same-tree
- **Difficulty**: easy
- **Patterns**: Trees
- **Version**: 1.0.0 (verified 2026-11-11T21:15:00Z)
- **Original Problem**: https://leetcode.com/problems/same-tree/

## 1. Core Invariant / The Trick

Base cases first: both null => `True`; one null => `False`; values differ => `False`. Otherwise recursively verify left and right child equality.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(min(P, Q))`
- **Space Complexity**: `O(min(Hp, Hq))`
- **Proof**: Mismatch terminates immediately; full match inspects every shared node once.

## 3. Minimal Idiomatic Code

### Python
```python
def isSameTree(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
```

### TypeScript
```typescript
export function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
  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);
}
```

### C++
```cpp
bool isSameTree(TreeNode* p, TreeNode* 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);
}
```

### Java
```java
boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
```

### Go
```go
func isSameTree(p, q *TreeNode) bool {
    if p == nil && q == nil { return true }
    if p == nil || q == nil || p.Val != q.Val { return false }
    return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Trying to validate via a single traversal list (e.g. inorder only) fails without null markers.

### Follow-ups
- Symmetric Tree checks `isMirror(root.left, root.right)` with `left.left vs right.right` and `left.right vs right.left`.