Reference: LeetCode
Difficulty: Easy

## Problem

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:

## Analysis

### Recursion

Note: Do the null check at the beginning.

Time: $O(N)$
Space: $O(h)$

### Iteration

Use two stacks to simulate the preorder traversal.

Note:

• Stack and Queue can contain null elements, while Deque can’t.
• Do null check first, and then do the value check. Make sure p and q are not null.
• The while condition should consider two stacks at the same time.
• The return statement should check if two stacks are empty at the same time.

Time: $O(N)$
Space: $O(h)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.